Description
大选要到了，受候选人X的要求，你调查了n个人，并记录了每个人的3个信息：
ai--他们能记忆π的多少位
bi--他们的头发数量
ci--他们是否会给候选人X投票
你需要找到某个公式使这些结果看起来有意义。你要选择2个实数S和T，将所有调查结果按ai*S+bi*T排序。如果ci
为true的人聚集在了一起，你会觉得这个排序看起来不错。更准确地说，如果j和k分别是第一个和最后一个ci为tr
ue的人的下标，你想要最小化k-j+1。注意有些S和T会让排序时出现相等的情况，这时你应该假设最坏情况发生，
即排序使得k-j+1最大。
Input
第一行一个数n(1 ≤ n ≤ 250000)为被调查的人数。
接下来每行描述一个人的ai(0 ≤ ai ≤ 2000000)、bi(0 ≤ bi ≤ 2000000)、ci
ci是一个0/1变量。保证至少有一个人投了X的票（即至少有一个ci为true）
Output
对于所有可能的实数对(S,T)，输出最小的k-j+1。
求出c=1的点的凸包，选出的S,T会使答案为一对包含了凸包的平行线间（含线上）的最小点数
当凸包只有一点时，若这个点不和其余c=1的点重合则答案为1，否则最坏情况下所有与凸包重合的点都被记入答案
当凸包上只有两点时，凸包为一条线段，线段上点数为所求
否则让平行线绕凸包类似旋转卡壳地扫描180度，对每个c=0的点，二分求出这个点进入和离开平行线时平行线对应的角度，得到每个点的出现区间，可以排序计算答案
#include<cstdio> #include<algorithm> #include<cmath> char buf[10000007],*ptr=buf-1; typedef long double ld; typedef long long i64; int _(){ int x=0,f=1,c=*++ptr; while(c<48)c=*++ptr; while(c>47)x=x*10+c-48,c=*++ptr; return x*f; } int abs(int x){return x>0?x:-x;} struct pos{ int x,y; int abs(){return (x>0?x:-x)+(y>0?y:-y);} void fix(){if(y<0||y==0&&x<0)x=-x,y=-y;} }ps1[250007],ps2[250007],ps[500007]; bool operator<(pos a,pos b){return a.y!=b.y?a.y<b.y:a.x<b.x;} bool operator==(pos a,pos b){return a.x==b.x&&a.y==b.y;} pos operator+(pos a,pos b){return (pos){a.x+b.x,a.y+b.y};} pos operator-(pos a,pos b){return (pos){a.x-b.x,a.y-b.y};} i64 operator*(pos a,pos b){return i64(a.x)*b.y-i64(a.y)*b.x;} i64 dot(pos a,pos b){return i64(a.x)*b.x+i64(a.y)*b.y;} bool cmp(pos a,pos b){ i64 x=a*b; return x?x>0:a.abs()<b.abs(); } int p1=0,p2=0,pp=0,n,ans=0; ld as[250007]; const ld pi=3.1415926535897932384626433832795l,_2pi=pi*2; void fix(ld&x,ld m){ while(x>=m)x-=m; while(x<0)x+=m; } struct ev{ pos a; int t; }es[500007]; bool operator<(ev a,ev b){ return a.a*b.a>0; } int s0=0,ep=0; int main(){ fread(buf,1,sizeof(buf),stdin); n=_(); for(int i=0,x,y,c;i<n;++i){ x=_();y=_();c=_(); if(c)ps1[p1++]=(pos){x,y}; else ps2[p2++]=(pos){x,y}; } int _p1=p1; ans=p1; std::sort(ps1,ps1+p1); p1=std::unique(ps1,ps1+p1)-ps1; std::sort(ps2,ps2+p2); pos p0=ps1[0]; for(int i=1;i<p1;++i)ps1[i]=ps1[i]-p0; std::sort(ps1+1,ps1+p1,cmp); ps[pp++]=(pos){0,0}; for(int i=1;i<p1;++i){ while(pp>=2&&(ps[pp-2]-ps[pp-1])*(ps1[i]-ps[pp-1])>=0)--pp; ps[pp++]=ps1[i]; } for(int i=0;i<pp;++i)ps[i]=ps[i]+p0; if(pp==1){ if(_p1>1)for(int i=0;i<p2;++i)if(ps2[i]==ps[0])++ans; return printf("%d",ans),0; } if(pp==2){ for(int i=0;i<p2;++i)if((ps2[i]-ps[1])*(ps2[i]-ps[0])==0&&dot(ps2[i]-ps[0],ps2[i]-ps[1])<=0)++ans; return printf("%d",ans),0; } ld xs=0,ys=0,a0; for(int i=0;i<pp;++i)xs+=ps[i].x,ys+=ps[i].y,ps[pp+i]=ps[i]; xs/=pp,ys/=pp; ps[pp*2]=ps[0]; ps[pp*2+1]=ps[1]; for(int i=0;i<pp;++i)as[i]=std::atan2(ps[i].y-ys,ps[i].x-xs); a0=as[0]; for(int i=0;i<pp;++i)fix(as[i]-=a0,_2pi); for(int i=0;i<p2;++i){ pos w=ps2[i]; ld a=std::atan2(w.y-ys,w.x-xs); fix(a-=a0,_2pi); int p=std::upper_bound(as,as+pp,a)-as; if((ps[p-1]-w)*(ps[p]-w)>=0){ ++ans; continue; } ld b=a+pi; fix(b,_2pi); int p2=std::upper_bound(as,as+pp,b)-as; int L=p,R=p2-1,M; if(L>R)R+=pp; while(L<R){ M=L+R>>1; if((ps[M+1]-w)*(ps[M]-w)>0)L=M+1; else R=M; } pos _l=ps[L]-w; _l.fix(); L=p2;R=p-1; if(L>R)R+=pp; while(L<R){ M=L+R>>1; if((ps[M+1]-w)*(ps[M]-w)<0)L=M+1; else R=M; } pos _r=ps[L]-w; _r.fix(); es[ep++]=(ev){_l,1},es[ep++]=(ev){_r,-1}; if(_l*_r<0)++s0; } std::sort(es,es+ep); int s1=s0; for(int i=0,j=0;i<ep;){ for(;j<ep&&es[i].a*es[j].a==0;++j); for(;i<j;++i)s0+=es[i].t; if(s0<s1)s1=s0; } printf("%d",ans+s1); return 0; }