POJ1912 A highway and the seven dwarfs (判断凸包与直线相交 logn)

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

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

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

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

于是得到算法：

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

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

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

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<queue>

#include<vector>

using namespace std;

const double eps=1e-9;

int cmp(double x)

{

 if(fabs(x)<eps)return 0;

 if(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<point>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<<res.x<<" "<<res.y<<endl;

 return res;

}

polygon_convex cut(polygon_convex &a,halfPlane &L)

{

 int n=a.P.size();

 polygon_convex res;

 for(int i=0;i<n;i++)

 	{

 	 if(calc(L,a.P[i])>-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<point> &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<n-1;i+=2)

 	{

 	 halfPlane L(a[i],a[(i+1)]);

 	 res=cut(res,L);

	}

 return res;

}

bool comp_less(const point &a,const point &b)

{

 return cmp(a.x-b.x)<0||cmp(a.x-b.x)==0&&cmp(a.y-b.y)<0;

}

polygon_convex convex_hull(vector<point> 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<a.size();i++)

 	{

 	 while(m>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<point> &a)

{

 for(int i=0;i<a.size();i++)

 	{

 	 int i1=(i+1)%int(a.size());

 	 int i2=(i+2)%int(a.size());

 	 int i3=(i+3)%int(a.size());

 	 if((cmp(det(a[i1]-a[i],a[i2]-a[i1]))*cmp(det(a[i2]-a[i1],a[i3]-a[i2])))<0)

	  	return false;

	}

 return true;

}

int containO(const polygon_convex &a,const point &b)

{

 int n=a.P.size();

 point g=(a.P[0]+a.P[n/3]+a.P[2*n/3])/3.0;

 int l=0,r=n;

 while(l+1<r)

 	{

 	 int mid=(l+r)/2;

 	 if(cmp(det(a.P[l]-g,a.P[mid]-g))>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<point> &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<n;++i)

 	{

 	 while(cmp(det(p[next(i)]-p[i],p[j]-p[i])-det(p[next(i)]-p[i],p[next(j)]-p[i]))<0)

 	 	j=next(j);

 	 double d=dist(p[i],p[j]);

 	 if(d>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<point>a)

{

 double sum=0;

 for(int i=0;i<a.size();i++)

 	sum+=det(a[(i+1)%(a.size())],a[i]);

 	return sum/2.;

}

int sumn;

int nex(int a,int b)

{

 a=a+b;

 while(a<0)a+=sumn;

 while(a>=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<point>pp;

int main()

{freopen("t.txt","r",stdin);

 int N;

 scanf("%d",&N);

 pp.resize(N);

 for(int i=0;i<N;i++)

 	 pp[i].input();

 polygon_convex pc=convex_hull(pp);

 point a,b;

 while(a.input()&&b.input())

 	 if(Convex_cross_Segment(a,b,pc))printf("GOOD\n");

 	 	else printf("BAD\n");

 return 0;

}

巴特西

POJ1912 A highway and the seven dwarfs (判断凸包与直线相交 logn)

最新文章

热门文章