【纪中集训2019.3.30】星辰大海

你的名字 2021-12-23 01:43 203阅读 0赞

## 题目 ##

### 描述 ###

有\$n\$个点\$p\_1 ,p\_2 , \\cdots ,\\,p\_n\$ ；

现在\$p\_1\$不见了，可能的横纵坐标范围是\$\[-10^6，10^6\]\$；

同时需要保证每三个点形成的有向角的符号不改变；

问\$p\_1\$可能范围的区域；

### 范围 ###

\$1 \\le T \\le 1000 \\ , \\ 3 \\le N , \\sum \\ N \\le 5 \\times 10^5 , |x\_i|,|y\_i| \\le 10^6\$ ；

误差范围：\$10^\{-6\}\$，建议eps取\$\[10^\{-15\},10^\{-12\}\]\$ ；

## 题解 ##

*  以\$p\_1\$为原点，得到$p\_2-p\_1,p\_3-p\_1,  \\cdots ，p\_n - p\_1 $ ；
 *  问题即求两两点的原点部分的半平面交；
 *  将新的\$p\_1，p\_2, \\cdots, p\_n\$按照极角排序；
 *  只需要考虑1.\$p\_i-p\_\{i+1\}\$，以及2.和\$p\_i\$极角相差不超过\$\\pi\$ 的最远点和\$p\_i\$组成的半平面；
 *  简要证明一下：
    
     *  假设\$p\_a-p\_b(a<b-1)\$有效却没有被考虑到，并且在\$ab\$中间的并没有漏掉的半平面；
     *  同时假设原点在左半平边；
     *  那么\$\\triangle p\_ap\_bO\$里面一定不能有点，否则假设为\$p\_c(a<c<b)\$；
     *  那么\$p\_c-p\_b和p\_a-p\_c\$会使其无效；
     *  所以一定存在\$p\_c(a<c<b)\$在$\\triangle $的外面；
     *  由于\$p\_b\$没有被\$2\$考虑到，所以一定同时存在\$p\_d\$被\$2\$考虑到了；
     *  那么\$p\_a-p\_c,p\_a-p\_d\$会使其无效；

### 一点想法 ###

能不能对所有的\$i=1-n\$求答案呢？；

感觉可以拓展的样子；

//我的半平面交好像很慢的样子QAQ; #include<bits/stdc++.h> #define ld double #define eps 1e-15 #define il inline using namespace std; const int N=1000010; int C,T,n,m,st[N],hd,tl; const ld pi=acos(-1); il int dcmp(ld x){return fabs(x)<eps?0:x<0?-1:1;} struct P{ ld x,y;ld ang; P(ld _x=0,ld _y=0):x(_x),y(_y){ang=atan2(y,x);}; P operator -(const P&A)const{return P(x-A.x,y-A.y);} P operator +(const P&A)const{return P(x+A.x,y+A.y);} P operator *(const ld&A)const{return P(x*A,y*A);} il bool operator <(const P&A)const{return dcmp(ang-A.ang)<0;} }p[N],q[N]; ld crs(const P&a,const P&b){return a.x*b.y-a.y*b.x;} struct L{ int a,b;ld ang; L(int _a=0,int _b=0):a(_a),b(_b){ang=atan2(p[b].y-p[a].y,p[b].x-p[a].x);} il bool operator <(const L&A)const{ int d=dcmp(ang-A.ang); return !d?dcmp(crs(p[b]-p[a],p[A.b]-p[a]))<0:d<0; } }l[N]; il char gc(){ static char*p1,*p2,s[1000000]; if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin); return(p1==p2)?EOF:*p1++; } il int rd(){ int x=0,f=1;char c=gc(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=gc();} return x*f; } il P get(const L&A,const L&B){ P u=p[A.b]-p[A.a]; P v=p[B.b]-p[B.a]; P w=p[A.a]-p[B.a]; ld d=crs(v,w)/crs(u,v); return p[A.a]+u*d; } il bool judge(const L&A,const P&B){ P u=p[A.b]-p[A.a]; P v=B-p[A.a]; return dcmp(crs(u,v))<=0; } il void add(int x,int y){ if(judge(L(x,y),P(0,0)))l[++m]=L(y,x); else l[++m]=L(x,y); } int main(){ freopen("everdream.in","r",stdin); freopen("everdream.out","w",stdout); C=rd();T=rd(); while(T--){ n=rd(); p[0].x=rd();p[0].y=rd(); for(int i=1,x,y;i<n;++i){ x=rd();y=rd(); x-=p[0].x;y-=p[0].y; p[i]=P(x,y); } --n;m=0;sort(p+1,p+n+1); for(int i=1;i<=n;++i)p[i+n]=p[i],p[i+n].ang+=2*pi; int fg=0; for(int i=1;i<=n;++i){ if(!dcmp(p[i].ang-p[i+1].ang)){fg=1;break;} add(i,i%n+1); P tmp=P(0,0);tmp.ang=p[i].ang+pi-eps; int j=lower_bound(p+1,p+n*2+1,tmp)-p; if(i+n!=j&&!dcmp(p[j].ang-p[i].ang-pi)){fg=1;break;} --j;if(i!=j&&i+n!=j)add(i,(j-1)%n+1); } if(fg){puts("0.0000000000");continue;} p[n+1]=(P){-1e6,-1e6};p[n+2]=(P){1e6,-1e6}; p[n+3]=(P){1e6,1e6};p[n+4]=(P){-1e6,1e6}; p[n+1]=p[n+1]-p[0];p[n+2]=p[n+2]-p[0]; p[n+3]=p[n+3]-p[0];p[n+4]=p[n+4]-p[0]; add(n+1,n+2),add(n+2,n+3); add(n+3,n+4),add(n+4,n+1); sort(l+1,l+m+1); hd=tl=0;st[++tl]=1; for(int i=2;i<=m;++i)if(dcmp(l[i].ang-l[i-1].ang)){ while(hd<tl-1 && judge( l[i] , get(l[st[tl]],l[st[tl-1]]) ) )tl--; while(hd<tl-1 && judge( l[i] , get(l[st[hd+1]],l[st[hd+2]]) ) )hd++; st[++tl]=i; } while(hd<tl-2 && judge( l[st[hd+1]] , get(l[st[tl]] , l[st[tl-1]]) ) )tl--; while(hd<tl-2 && judge( l[st[tl]] , get(l[st[hd+1]] , l[st[hd+2]]) ) )hd++; if(tl-hd<=2){puts("0.0000000000");continue;} n=0;st[tl+1]=st[hd+1]; for(int i=hd+1;i<=tl;++i)q[++n]=get(l[st[i]],l[st[i+1]]); ld ans=0;q[n+1]=q[1]; for(int i=1;i<=n;++i)ans+=crs(q[i],q[i+1]); ans/=2; printf("%.10lf\n",ans); } //printf("%.2lf\n",1.0*clock()/CLOCKS_PER_SEC); return 0; }

转载于:https://www.cnblogs.com/Paul-Guderian/p/10637835.html