uva 10256 The Great Divide

2019-11-11 07:42:18

字體：大中小

來源：轉載

供稿：網友

原題： 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的情況下，是否有兩個相等的點，以及線段相交或者相連

考慮上述情況即可

上一篇：2017/01/25

下一篇：emf32的usb音頻采集