【纪中集训2019.3.30】星辰大海

题目

描述

? 有\(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;
}

【纪中集训2019.3.30】星辰大海

原文：https://www.cnblogs.com/Paul-Guderian/p/10637835.html