首页 > 代码库 > BZOJ2934 : [Poi1999]祭坛问题
BZOJ2934 : [Poi1999]祭坛问题
对于每个祭坛，算出每条线段阻碍它的角度区间，然后排序求并看看是否有空位即可，时间复杂度$O(n^2\log n)$。
这题在Main上官方时限是0.2S，因此需要几个常数优化：
$1.$为了避免用atan2(y,x)算角度，改成算斜率，所以需要分$4$个方向讨论。
$2.$对区间排序时，不要直接对结构体排序，而是对其指针排序。
$3.$在计算某个祭坛时，除了它本身需要特别计算之外，其它祭坛可以直接看成没有缺口的矩形，可以减少$n$个事件。
$4.$在计算的过程中，不断收缩左右边界，当左右边界重合时即可直接判定为不可能。
#include<cstdio>#include<algorithm>using namespace std;const int N=1005,BUF=50000;const double eps=1e-9,inf=1e9;int n,m,cnt,i,X,k,ce,flag;char dir[N],Buf[BUF],*buf=Buf;double L,R;inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}inline void read(char&a){while(*buf<‘A‘)buf++;a=*buf++;}struct P{int x,y;P(){}P(int _x,int _y){x=_x,y=_y;}}a[N];struct seg{ P x,y; seg(){} seg(P _x,P _y){ x=_x,y=_y; if(x.x>y.x||x.y>y.y)swap(x,y); }}b[N*5],c[N*4],f[N];struct E{ double l,r; void set(double _l,double _r){ l=_l,r=_r; if(l<L+eps)L=max(L,r); if(r>R-eps)R=min(R,l); if(L+eps>R)k=1; }}e[N*4],*q[N*4];inline bool cmp(E*x,E*y){return x->l<y->l;}inline bool cal(int x,int y,double&t){ if(x<=0)return 0; t=1.0*y/x; return 1;}inline double fix(double x){return x>0?inf:-inf;}void initS(int x,int y){ cal(-f[X].x.y+y,f[X].x.x-x,L); cal(-f[X].y.y+y,f[X].y.x-x,R); if(L>R)swap(L,R); for(int i=1;i<=m;i++)if((i+4)/5==X){ seg&j=b[i];double l,r; if(!cal(-j.x.y+y,j.x.x-x,l))continue; if(!cal(-j.y.y+y,j.y.x-x,r))r=fix(l); if(l>r)swap(l,r); if(r<L-eps||l>R+eps)continue; e[ce++].set(l,r); } for(int i=1;i<=cnt&&!k;i++)if((i+3)/4!=X){ seg&j=c[i];double l,r; if(!cal(-j.x.y+y,j.x.x-x,l))continue; if(!cal(-j.y.y+y,j.y.x-x,r))r=fix(l); if(l>r)swap(l,r); if(r<L-eps||l>R+eps)continue; e[ce++].set(l,r); }}void initN(int x,int y){ cal(f[X].y.y-y,f[X].y.x-x,L); cal(f[X].x.y-y,f[X].x.x-x,R); if(L>R)swap(L,R); for(int i=1;i<=m;i++)if((i+4)/5==X){ seg&j=b[i];double l,r; if(!cal(j.y.y-y,j.y.x-x,r))continue; if(!cal(j.x.y-y,j.x.x-x,l))l=fix(r); if(l>r)swap(l,r); if(r<L-eps||l>R+eps)continue; e[ce++].set(l,r); } for(int i=1;i<=cnt&&!k;i++)if((i+3)/4!=X){ seg&j=c[i];double l,r; if(!cal(j.y.y-y,j.y.x-x,r))continue; if(!cal(j.x.y-y,j.x.x-x,l))l=fix(r); if(l>r)swap(l,r); if(r<L-eps||l>R+eps)continue; e[ce++].set(l,r); }}void initW(int x,int y){ cal(-f[X].x.x+x,f[X].x.y-y,L); cal(-f[X].y.x+x,f[X].y.y-y,R); if(L>R)swap(L,R); for(int i=1;i<=m;i++)if((i+4)/5==X){ seg&j=b[i];double l,r; if(!cal(-j.x.x+x,j.x.y-y,l))continue; if(!cal(-j.y.x+x,j.y.y-y,r))r=fix(l); if(l>r)swap(l,r); if(r<L-eps||l>R+eps)continue; e[ce++].set(l,r); } for(int i=1;i<=cnt&&!k;i++)if((i+3)/4!=X){ seg&j=c[i];double l,r; if(!cal(-j.x.x+x,j.x.y-y,l))continue; if(!cal(-j.y.x+x,j.y.y-y,r))r=fix(l); if(l>r)swap(l,r); if(r<L-eps||l>R+eps)continue; e[ce++].set(l,r); }}void initE(int x,int y){ cal(f[X].y.x-x,f[X].y.y-y,L); cal(f[X].x.x-x,f[X].x.y-y,R); if(L>R)swap(L,R); for(int i=1;i<=m;i++)if((i+4)/5==X){ seg&j=b[i];double l,r; if(!cal(j.y.x-x,j.y.y-y,r))continue; if(!cal(j.x.x-x,j.x.y-y,l))l=fix(r); if(l>r)swap(l,r); if(r<L-eps||l>R+eps)continue; e[ce++].set(l,r); } for(int i=1;i<=cnt&&!k;i++)if((i+3)/4!=X){ seg&j=c[i];double l,r; if(!cal(j.y.x-x,j.y.y-y,r))continue; if(!cal(j.x.x-x,j.x.y-y,l))l=fix(r); if(l>r)swap(l,r); if(r<L-eps||l>R+eps)continue; e[ce++].set(l,r); }}bool check(){ if(k)return 0; for(int i=0;i<ce;i++)q[i]=e+i; sort(q,q+ce,cmp); for(int i=0;i<ce;i++){ if(q[i]->l>L+eps)return 1; if(L<q[i]->r)L=q[i]->r; } return 0;}int main(){ fread(Buf,1,BUF,stdin);read(n); for(i=1;i<=n;i++){ int x1,y1,x2,y2,o;char d; read(x1),read(y1),read(x2),read(y2),read(d); x1<<=2,y1<<=2,x2<<=2,y2<<=2; if(x1>x2)swap(x1,x2); if(y1>y2)swap(y1,y2); a[i]=P((x1+x2)/2,(y1+y2)/2); dir[i]=d; if(d!=‘S‘)b[++m]=seg(P(x1,y1),P(x2,y1)); else{ o=(x1+x2)/2; b[++m]=seg(P(x1,y1),P((x1+o)/2,y1)); b[++m]=seg(P(x2,y1),P((x2+o)/2,y1)); f[i]=seg(P((x1+o)/2,y1),P((x2+o)/2,y1)); } if(d!=‘N‘)b[++m]=seg(P(x1,y2),P(x2,y2)); else{ o=(x1+x2)/2; b[++m]=seg(P(x1,y2),P((x1+o)/2,y2)); b[++m]=seg(P(x2,y2),P((x2+o)/2,y2)); f[i]=seg(P((x1+o)/2,y2),P((x2+o)/2,y2)); } if(d!=‘W‘)b[++m]=seg(P(x1,y1),P(x1,y2)); else{ o=(y1+y2)/2; b[++m]=seg(P(x1,y1),P(x1,(y1+o)/2)); b[++m]=seg(P(x1,y2),P(x1,(y2+o)/2)); f[i]=seg(P(x1,(y1+o)/2),P(x1,(y2+o)/2)); } if(d!=‘E‘)b[++m]=seg(P(x2,y1),P(x2,y2)); else{ o=(y1+y2)/2; b[++m]=seg(P(x2,y1),P(x2,(y1+o)/2)); b[++m]=seg(P(x2,y2),P(x2,(y2+o)/2)); f[i]=seg(P(x2,(y1+o)/2),P(x2,(y2+o)/2)); } c[++cnt]=seg(P(x1,y1),P(x2,y1)); c[++cnt]=seg(P(x1,y2),P(x2,y2)); c[++cnt]=seg(P(x1,y1),P(x1,y2)); c[++cnt]=seg(P(x2,y1),P(x2,y2)); } for(X=1;X<=n;X++){ ce=k=0; if(dir[X]==‘S‘)initS(a[X].x,a[X].y); if(dir[X]==‘N‘)initN(a[X].x,a[X].y); if(dir[X]==‘W‘)initW(a[X].x,a[X].y); if(dir[X]==‘E‘)initE(a[X].x,a[X].y); if(check())flag=1,printf("%d\n",X); } if(!flag)puts("BRAK"); return 0;}
BZOJ2934 : [Poi1999]祭坛问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。