uva 10256 The Great Divide

2019-11-14 09:09:53

字体：大中小

来源：转载

供稿：网友

原题： Somewhere in Gaul, there is a little village very like the village where Asterix and Obelix live. Not very long ago they had only one chief Altruistix and peace reigned in the village. But now those happy days are just dreams. The villagers are now divided. Some of the villagers have elected Majestix as their chief and the others have elected Cleverdix. The two chiefs have decided to divide the village into two parts by digging a straight ditch through the middle of the village so that the houses of the supporters of Majestix lie on one part and those of the followers of Cleverdix lie on the other. So, they have invited Getafix, the venerable druid of Asterix’s village, to figure out whether such a dividing line exists or not. Since Getafix knows that you are so good in PRogramming, he seeks your help. Input The input may contain multiple test cases. The first line of each test case contains two integers M and C (1 ≤ M,C ≤ 500), indicating the number of houses of the supporters of Majestix and Cleverdix respectively.Each of the next M lines contains two integers x and y (−1000 ≤ x,y ≤ 1000) giving the coordinates of the house of a supporter of Majestix. For convenience each house is considered as a single point on the plane. Each of the next C lines contains two integers x and y (−1000 ≤ x,y ≤ 1000) giving the co-ordinates of the house of a supporter of Cleverdix. The input will terminate with two zeros for M and C. Output For each test case in the input output a line containing either ‘Yes’ or ‘No’ depending on whether there exists a straight line that divides the two set of houses. The dividing line can NOT contain points of both sides. Sample Input 4 3 100 600 200 400 600 500 300 700 400 100 600 200 500 300 4 3 100 600 400 100 600 200 500 300 200 400 600 500 300 700 0 0 Sample Output Yes No

中文： 给你一堆红点和一堆蓝点，问你能不能用一条直线把这两堆点区分开来。

#include <bits/stdc++.h>using namespace std;const double PI=acos(-1);const double eps=0.0001;int n,m;int dcmp(double x){ if(fabs(x)<eps) return 0; else return x<0?-1:1;}double torad(double deg){ return deg/180*PI;}struct Point{ double x,y; Point(double x=0,double y=0):x(x),y(y){} bool Operator==(const Point &p) const { return this->x==p.x&&this->y==p.y; }};#define Vector Pointdouble Cross(Vector A,Vector B){ return A.x*B.y-A.y*B.x;}bool operator < (const Point &a,const Point &b)//排序用，按照x的坐标从小到大，如果x相同，那么按照y从小到大{ return a.x<b.x||(a.x==b.x&&a.y<b.y);}Vector operator +(Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}//坐标点相加Vector operator -(Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}//相减double Dot(Vector A,Vector B) {return A.x*B.x+A.y*B.y;}int ConvexHull(Point *p,int n,Point *ch)//p是所有点，n所有点的个数，ch里面记录形成凸包的点，返回凸包点的个数{ sort(p,p+n); int m=0; for(int i=0;i<n;i++) { while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--; ch[m++]=p[i]; } int k=m; for(int i=n-2;i>=0;i--) { while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--; ch[m++]=p[i]; } if(n>1) m--; return m;}bool OnSegment(Point p,Point a1,Point a2){ return dcmp(Cross(a1-p,a2-p)==0&&dcmp(Dot(a1-p,a2-p))<0);}bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2){ if(OnSegment(a1,b1,b2)||OnSegment(a2,b1,b2)||OnSegment(b1,a1,a2)||OnSegment(b2,a1,a2)) return true; double c1 = Cross(a2-a1,b1-a1), c2 = Cross(a2-a1,b2-a1), c3 = Cross(b2-b1,a1-b1), c4 = Cross(b2-b1,a2-b1); return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;}int isPointInPolygon(Point p,Point *ch,int n){ int wn=0; for(int i=0;i<n;i++) { if(OnSegment(p,ch[i],ch[(i+1)%n]))return -1; int k=dcmp(Cross(ch[(i+1)%n]-ch[i],p-ch[i])); int d1=dcmp(ch[i].y-p.y); int d2=dcmp(ch[(i+1)%n].y-p.y); if(k>0&&d1<=0&&d2>0) wn++; if(k<0&&d2<=0&&d1>0) wn--; } if(wn!=0) return 1; return 0;}int main(){ ios::sync_with_stdio(false); Point red[501],blue[501],red_hull[501],blue_hull[501]; while(cin>>n>>m,n+m) { for(int i=0;i<n;i++) cin>>red[i].x>>red[i].y; for(int i=0;i<m;i++) cin>>blue[i].x>>blue[i].y; if(n==1&&m==1) { if(red[0].x==blue[0].x&&red[0].y==blue[0].y) { cout<<"No"<<endl; continue; } } int red_num=ConvexHull(red,n,red_hull); int blue_num=ConvexHull(blue,m,blue_hull); int flag=1; for(int i=0;i<red_num;i++)//是否相交，或者有相等的点 { for(int j=0;j<blue_num;j++) { if(SegmentProperIntersection(red_hull[i],red_hull[(i+1)%red_num],blue_hull[j],blue_hull[(j+1)%blue_num])||red_hull[i]==blue_hull[j]) {// cout<<red_hull[i].x<<" "<<red_hull[i].y<<" "<<red_hull[(i+1)%red_num].x<<" "<<red_hull[(i+1)%red_num].y<<endl<<endl;// cout<<blue_hull[j].x<<" "<<blue_hull[j].y<<" "<<blue_hull[(j+1)%blue_num].x<<" "<<blue_hull[(j+1)%blue_num].y<<endl<<endl; flag=0; break; } } if(flag==0) break; } if(isPointInPolygon(red_hull[0],blue_hull,blue_num)||isPointInPolygon(blue_hull[0],red_hull,red_num))//两个凸包互相包含 flag=0; if(!flag) cout<<"No"<<endl; else cout<<"Yes"<<endl;/* for(int i=0;i<red_num;i++) cout<<red_hull[i].x<<" "<<red_hull[i].y<<endl; cout<<endl; for(int i=0;i<blue_num;i++) cout<<blue_hull[i].x<<" "<<blue_hull[i].y<<endl;*/ } return 0;}

解答：

好久没做计算几何的题目，在训练指南上面找了一个例题做做。

要想满足能够用一条直线分离两类点那么：

首先把红点和蓝点构造凸包 1.两个凸包不相交 2.两个凸包互不包含 3.输入点的个数小于3的情况下，是否有两个相等的点，以及线段相交或者相连

考虑上述情况即可

上一篇：您只能在 HTML 输出中使用 document.write。如果您在文档加载后使用该方法，会覆盖整个文档。

下一篇：runtime error可能的原因