给两类点，问是否存在一条直线把两类点划分，满足：1. 直线上没有点；2. 一类点在直线一侧，另一类点在直线另一侧。这种题嘛，把两类点分别求个凸包，然后判断两个凸包是否有交点就行了。分析下，考虑两个凸包点数都>=3的时候，只需要判断，，一，A凸包的点是否在B上或内部，反之要盼，二，是否有A凸包的一个线段和B凸包的一个线段相交。当存在一个凸包点数<=2的时候，会有点麻烦，但可以找到一个简便的方法，不需要讨论太多的方法，来解决。（最坏也就是枚举嘛，点和点，点和直线，点和凸包，直线和直线，直线和凸包，凸包和凸包。在这个基础上节省一下，发现只需要枚举点和点，点和直线，其余和凸包）..以下是Aizu 1298的 代码，UVA10256那题输出时候字符有点不同。My Code;ll;uin;read(){int x=0,f=1;char ch=getchar();while(ch>’9’||ch<‘0′){if(ch==’-‘)f=-1;ch=getchar();}while(ch>=’0’&&ch<=’9’){x=x*10+ch-‘0’;ch=getchar();}return x*f;}const double eps=1e-9;inline int dcmp(double x){if(fabs(x)<eps) return 0;else if(x<0) return -1;;}int n,m;struct Point{double x,y;Point(){};Point(double xx,double yy){x=xx,y=yy;}};inline bool comp(const Point a,const Point b){if(dcmp(a.x-b.x)) return a.x<b.x;else return a.y<b.y;}typedef Point Vector;Vector operator+(const Vector a,const Vector b){return Vector(a.x+b.x,a.y+b.y);}Vector operator-(const Vector a,const Vector b){return Vector(a.x-b.x,a.y-b.y);}double operator*(const Vector a,const Vector b){return a.x*b.x+a.y*b.y;}double operator%(const Vector a,const Vector b){return a.x*b.y-a.y*b.x;}Vector operator*(const Vector a,const double b){return Vector(a.x*b,a.y*b);}Vector operator*(const double b,const Vector a){return Vector(a.x*b,a.y*b);}bool operator ==(const Vector a,const Vector b){return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);}Vector operator/(const Vector a,const double b){return Vector(a.x/b,a.y/b);}double Square_Triangle(Point p1,Point p2,Point p3){*fabs((p2-p1)%(p3-p1));}#define lenp res.size()void Convex_Hull(Point *p,int n,vector<Point>&res){res.clear();sort(p,p+n,comp);for(int i=0;i<n;i++){while(lenp>1&&dcmp((res[lenp-1]-res[lenp-2])%(p[i]-res[lenp-1]))<=0) res.pop_back();res.push_back(p[i]);}int k=(int)lenp;for(int i=n-2;i>=0;i–){while(lenp>k&&dcmp((res[lenp-1]-res[lenp-2])%(p[i]-res[lenp-1]))<=0) res.pop_back();res.push_back(p[i]);}if(lenp>1) res.pop_back();}void readPointInt(Point &p){int x,y;x=read(),y=read();p=Point(x,y);}Point p1[N],p2[N];Square_ConvexHull(res=0.0;for(int i=1;i<lenv-1;i++){res+=Square_Triangle(v[0],v[i],v[i+1]);}return res;}double Square_PointWithConvexHull(Point p,vector<Point>&v){//求一点绕凸包扫一圈形成的面积v.push_back(v[0]);double res=0.0;for(int i=0;i<lenv-1;i++){res+=Square_Triangle(p,v[i],v[i+1]);}v.pop_back();return res;}bool PointOnSegment(Point p,Point p1,Point p2){Vector v1=p1-p,v2=p2-p;if(dcmp(v1%v2)) return false;;;}bool PointInConvexHull1_In_ConvexHull2(vector<Point>&v1,vector<Point>&v2){if(lenv1==1&&lenv2==1) return v1[0]==v2[0];if(lenv1==1&&lenv2==2) return PointOnSegment(v1[0],v2[0],v2[1]);if(lenv2>=3){double Sv2=Square_ConvexHull(v2);for(int i=0;i<lenv1;i++){double St=Square_PointWithConvexHull(v1[i],v2);if(!dcmp(St-Sv2)) return true;}}return false;}bool Segment1_Inter_Segment2(Point p1,Point p2,Point q1,Point q2){if(!dcmp((p1-p2)%(q1-q2))){return PointOnSegment(p1,q1,q2)||PointOnSegment(p2,q1,q2)||PointOnSegment(q1,p1,p2)||PointOnSegment(q2,p1,p2);}else{int t1=dcmp((p2-p1)%(q1-p1));int t2=dcmp((p2-p1)%(q2-p1));int t3=dcmp((q2-q1)%(p1-q1));int t4=dcmp((q2-q1)%(p2-q1));return t1*t2<=0&&t3*t4<=0;}}bool ConvexHull1_Inter_ConvexHull2(vector<Point>&v1,vector<Point>&v2){;if(PointInConvexHull1_In_ConvexHull2(v2,v1)) return true;//两凸包线段是否相交if(lenv1>=2&&lenv2>=2){v1.push_back(v1[0]);v2.push_back(v2[0]);for(int i=0;i<lenv1-1;i++){for(int j=0;j<lenv2-1;j++){if(Segment1_Inter_Segment2(v1[i],v1[i+1],v2[j],v2[j+1])){v1.pop_back();v2.pop_back();return true;}}}v1.pop_back();v2.pop_back();}return false;}int main(){while(1){n=read(),m=read();if(!n&&!m) break;for(int i=0;i<n;i++){readPointInt(p1[i]);}vector<Point>res1;Convex_Hull(p1,n,res1);for(int i=0;i<m;i++){readPointInt(p2[i]);}vector<Point>res2;Convex_Hull(p2,m,res2);if(ConvexHull1_Inter_ConvexHull2(res1,res2)){printf(“NO\n”);}else printf(“YES\n”);}return 0;}
只有不断找寻机会的人才会及时把握机会。
