给定n个点 和若干条直线，判断对于一条直线，是否存在两个点在直线的两侧。

显然原命题等价于 凸包与直线是否相交。

O（n）的算法是显而易见的 但是直线数量太多 就会复杂到O（n^2）由于n<=100000 会TLE

 

凸包有个很好的性质，我们没有利用， 那就是凸包的边相对于要判断的直线是极角有序的！

于是得到算法：

构造好凸包后，二分找凸包上第一个与正向直线夹角大于0的线段和第一个与反向直线夹角大于0的线段

然后判断两线段的起点是否在直线两侧即可。

 

代码实现有一点注意的细节:不要用上下界的方法实现二分，会很困难，用另外一种调整跳转距离的方法来实现就会简单很多。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;const double eps=1e-9;int cmp(double x){ if(fabs(x)
             
              0)return 1; else return -1;}const double pi=acos(-1.0);inline double sqr(double x){ return x*x;}struct point{ double x,y; point (){} point (double a,double b):x(a),y(b){} bool input() { return scanf("%lf%lf",&x,&y)!=EOF; } friend point operator +(const point &a,const point &b) { return point(a.x+b.x,a.y+b.y); } friend point operator -(const point &a,const point &b) { return point(a.x-b.x,a.y-b.y); } friend bool operator ==(const point &a,const point &b) { return cmp(a.x-b.x)==0&&cmp(a.y-b.y)==0; } friend point operator *(const point &a,const double &b) { return point(a.x*b,a.y*b); } friend point operator*(const double &a,const point &b) { return point(a*b.x,a*b.y); } friend point operator /(const point &a,const double &b) { return point(a.x/b,a.y/b); } double norm() { return sqr(x)+sqr(y); }};struct line{ point a,b; line(){}; line(point x,point y):a(x),b(y) { }};double det(const point &a,const point &b){ return a.x*b.y-a.y*b.x;}double dot(const point &a,const point &b){ return a.x*b.x+a.y*b.y; }double dist(const point &a,const point &b){ return (a-b).norm();}point rotate_point(const point &p,double A){ double tx=p.x,ty=p.y; return point(tx*cos(A)-ty*sin(A),tx*sin(A)+ty*cos(A));}bool parallel(line a,line b){ return !cmp(det(a.a-a.b,b.a-b.b));}bool line_joined(line a,line b,point &res){ if(parallel(a,b))return false; double s1=det(a.a-b.a,b.b-b.a); double s2=det(a.b-b.a,b.b-b.a); res=(s1*a.b-s2*a.a)/(s1-s2); return true;}bool pointonSegment(point p,point s,point t){ return cmp(det(p-s,t-s))==0&&cmp(dot(p-s,p-t))<=0;}void PointProjLine(const point p,const point s,const point t,point &cp){ double r=dot((t-s),(p-s))/dot(t-s,t-s); cp=s+r*(t-s);}struct polygon_convex{ vector
              
               P; polygon_convex(int Size=0) { P.resize(Size); } };struct halfPlane{ double a,b,c; halfPlane(point p,point q) { a=p.y-q.y; b=q.x-p.x; c=det(p,q); } halfPlane(double aa,double bb,double cc) { a=aa;b=bb;c=cc; } };double calc(halfPlane &L,point &a){ return a.x*L.a +a.y*L.b+L.c;}point Intersect(point &a,point &b,halfPlane &L){ point res; double t1=calc(L,a),t2=calc(L,b); res.x=(t2*a.x-t1*b.x)/(t2-t1); res.y=(t2*a.y-t1*b.y)/(t2-t1); //cout<
               
                <<" "<
                
                 <
                 
                  -eps)res.P.push_back(a.P[i]); else { int j; j=i-1; if(j<0)j=n-1; if(calc(L,a.P[j])>-eps) res.P.push_back(Intersect(a.P[j],a.P[i],L)); j=i+1; if(j==n)j=0; if(calc(L,a.P[j])>-eps) res.P.push_back(Intersect(a.P[i],a.P[j],L)); } } return res;}double INF=10000;polygon_convex core(vector
                  
                    &a){ polygon_convex res; res.P.push_back(point(0,0)); res.P.push_back(point(INF,0)); res.P.push_back(point(INF,INF)); res.P.push_back(point(0,INF)); int n=a.size(); for(int i=0;i
                   
                     a){ polygon_convex res(2*a.size()+5); sort(a.begin(),a.end(),comp_less); a.erase(unique(a.begin(),a.end()),a.end());//删去重复点 int m=0; for(int i=0;i
                    
                     1&&cmp(det(res.P[m-1]-res.P[m-2],a[i]-res.P[m-2]))<=0)--m; res.P[m++]=a[i]; } int k=m; for(int i=int(a.size())-2;i>=0;--i) { while(m>k&&cmp(det(res.P[m-1]-res.P[m-2],a[i]-res.P[m-2]))<=0)--m; res.P[m++]=a[i]; } res.P.resize(m); if(a.size()>1)res.P.resize(m-1); return res;}bool is_convex(vector
                     
                       &a){ for(int i=0;i
                      
                       0) { if(cmp(det(a.P[l]-g,b-g))>=0&&cmp(det(a.P[mid]-g,b-g))<0)r=mid; else l=mid; }else { if(cmp(det(a.P[l]-g,b-g))<0&&cmp(det(a.P[mid]-g,b-g))>=0)l=mid; else r=mid; } } r%=n; int z=cmp(det(a.P[r]-b,a.P[l]-b))-1; if(z==-2)return 1; return z; }long long int distant(point a,point b){ return (int(b.x)-int(a.x))*(int(b.x)-int(a.x))+(int(b.y)-int(a.y))*(int(b.y)-int(a.y));}double convex_diameter(polygon_convex &a,int &First,int &Second){ vector
                       
                         &p=a.P; int n=p.size(); double maxd=0; if(n==1) { First=Second=0; return maxd; } #define next(i)((i+1)%n) for(int i=0,j=1;i
                        
                         maxd) { maxd=d; First=i,Second=j; } d=dist(p[next(i)],p[next(j)]); if(d>maxd) { maxd=d; First=next(i),Second=next(j); } } return maxd;}double area(vector
                         
                          a){ double sum=0; for(int i=0;i
                          
                           =sumn)a-=sumn; return a;}bool Convex_cross_Segment(point a,point b,polygon_convex &pc){ sumn=pc.P.size(); if(pc.P.size()<2)return true; if(pc.P.size()==2) { if(cmp(det(a-b,pc.P[0]-a)*det(a-b,pc.P[1]-a))<0)return false; else return true; } int len=pc.P.size()/2,loc1=-1,loc2=-1,locn=pc.P.size()/2; while(true) { if(cmp(det(a-b,pc.P[nex(locn,1)]-pc.P[locn]))>0&&cmp(det(a-b,pc.P[locn]-pc.P[nex(locn,-1)]))<=0) {loc1=locn;break;} if(cmp(det(a-b,pc.P[nex(locn,1)]-pc.P[locn]))>0) {locn=nex(locn,-len);if(len>1)len/=2;continue;} else{locn=nex(locn,len);if(len>1)len/=2;continue;} } len=pc.P.size()/2; while(true) { if(cmp(det(a-b,pc.P[nex(locn,1)]-pc.P[locn]))<0&&cmp(det(a-b,pc.P[locn]-pc.P[nex(locn,-1)]))>=0) {loc2=locn;break;} if(cmp(det(a-b,pc.P[nex(locn,1)]-pc.P[locn]))<0) {locn=nex(locn,-len);if(len>1)len/=2;continue;} else{locn=nex(locn,len);if(len>1)len/=2;continue;} } if(cmp(det(a-b,pc.P[loc1]-a)*det(a-b,pc.P[loc2]-a))<0)return false; else return true;}vector
                           
                            pp;int main(){freopen("t.txt","r",stdin); int N; scanf("%d",&N); pp.resize(N); for(int i=0;i