BZOJ3536 : [Usaco2014 Open]Cow Optics

时间:2023-05-13 10:30:50

枚举最后光线射到终点的方向,求出从起点出发以及从终点出发的光路,扫描线+树状数组统计交点个数即可。

注意当光路成环时,对应的两个方向应该只算一次。

时间复杂度$O(n\log n)$。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100010;
const ll inf=1LL<<50;
inline void read(int&a){
char c;bool f=0;a=0;
while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-')));
if(c!='-')a=c-'0';else f=1;
while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';
if(f)a=-a;
}
int n,i,j,k,q[N],g[N][4],dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};char d[N],w[N*2];
int cb,cc,ce,cf,bit[N*6];ll f[N*6],ans;
struct P{
ll x,y;
P(){}
P(ll _x,ll _y){x=_x,y=_y;}
void read(){
int a,b;
::read(a),::read(b);
x=a,y=b;
}
}B,a[N],b[N*2],c[N*2];
struct E{
ll x,l,r;int t;
E(){}
E(ll _x,ll _l,ll _r,int _t){x=_x,l=_l,r=_r,t=_t;}
}e[N*6];
inline bool cmpx(int x,int y){return a[x].x==a[y].x?a[x].y<a[y].y:a[x].x<a[y].x;}
inline bool cmpy(int x,int y){return a[x].y==a[y].y?a[x].x<a[y].x:a[x].y<a[y].y;}
inline bool cmpe(const E&a,const E&b){return a.x==b.x?a.t>b.t:a.x<b.x;}
int work(P o,int k,P*q,int&m){
q[m=1]=o;
int i,j=-1;ll dis;
for(i=0;i<=n;i++){
if(k==0&&!(a[i].x==o.x&&a[i].y<=o.y))continue;
if(k==1&&!(a[i].x==o.x&&a[i].y>=o.y))continue;
if(k==2&&!(a[i].y==o.y&&a[i].x<=o.x))continue;
if(k==3&&!(a[i].y==o.y&&a[i].x>=o.x))continue;
ll t=1LL*abs(a[i].x-o.x)+1LL*abs(a[i].y-o.y);
if(!t)continue;
if(j<0||t<dis)j=i,dis=t;
}
while(~j){
q[++m]=a[j];
w[m]=k;
if(!j)return 2;
if(m>2&&q[m].x==q[2].x&&q[m].y==q[2].y&&w[m]==w[2])return 1;
if(d[j]=='/')k=(k+2)&3;else k=3-k;
o=a[j];
j=g[j][k];
}
q[++m]=o;
q[m].x+=inf*dx[k];
q[m].y+=inf*dy[k];
return 2;
}
inline void adda(const P&A,const P&B){
if(A.y!=B.y)return;
ll l=A.x,r=B.x;
if(l>r)swap(l,r);
l++,r--;
if(l>r)return;
e[++ce]=E(l,A.y,0,1);
e[++ce]=E(r,A.y,0,-1);
f[++cf]=A.y;
}
inline void addb(const P&A,const P&B){
if(A.x!=B.x)return;
ll l=A.y,r=B.y;
if(l>r)swap(l,r);
l++,r--;
if(l>r)return;
e[++ce]=E(A.x,l,r,0);
f[++cf]=l,f[++cf]=r;
}
inline int lower(ll x){
int l=1,r=cf,mid,t;
while(l<=r)if(f[mid=(l+r)>>1]<=x)l=(t=mid)+1;else r=mid-1;
return t;
}
inline void add(int x,int p){for(;x<=cf;x+=x&-x)bit[x]+=p;}
inline int ask(int x){int t=0;for(;x;x-=x&-x)t+=bit[x];return t;}
ll cal(){
int i;
sort(f+1,f+cf+1);
for(i=1;i<=cf;i++)bit[i]=0;
sort(e+1,e+ce+1,cmpe);
ll ret=0;
for(i=1;i<=ce;i++)if(e[i].t)add(lower(e[i].l),e[i].t);else ret+=ask(lower(e[i].r))-ask(lower(e[i].l)-1);
return ret;
}
ll solve(int x){
int i;
ce=cf=0;
for(i=1;i<cb;i++)adda(b[i],b[i+1]);
for(i=3-x;i<cc;i++)addb(c[i],c[i+1]);
ll ret=cal();
ce=cf=0;
for(i=1;i<cb;i++)addb(b[i],b[i+1]);
for(i=3-x;i<cc;i++)adda(c[i],c[i+1]);
return ret+cal();
}
int main(){
read(n);
B.read();
for(i=1;i<=n;i++){
char c[9];
a[i].read();
scanf("%s",c);
d[i]=c[0];
q[i]=i;
}
sort(q,q+n+1,cmpx);
for(i=0;i<=n;i++)for(j=0;j<4;j++)g[i][j]=-1;
for(i=0;i<=n;){
for(j=i;j<=n&&a[q[i]].x==a[q[j]].x;j++);
for(i++;i<j;i++){
g[q[i]][0]=q[i-1];
g[q[i-1]][1]=q[i];
}
}
sort(q,q+n+1,cmpy);
for(i=0;i<=n;){
for(j=i;j<=n&&a[q[i]].y==a[q[j]].y;j++);
for(i++;i<j;i++){
g[q[i]][2]=q[i-1];
g[q[i-1]][3]=q[i];
}
}
work(P(0,0),1,b,cb);
for(i=0;i<4;i++){
int x=work(B,i,c,cc);
ans+=solve(x)*x;
}
return printf("%lld",ans/2),0;
}