UVA 10256 The Great Divide （凸包，多边形的位置关系）

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=34148

【思路】

凸包

求出红蓝点的凸包，剩下的问题就是判断两个凸包是否相离。

需要确定两点：

　　　　1）凸包上线段是否相交->相交

　　　　2）凸包上的点是否包含在另一个凸包里->内含。

【代码】

  1 #include<cmath>
  2 #include<vector>
  3 #include<cstdio>
  4 #include<algorithm>
  5 using namespace std;
  6 
  7 const double eps = 1e-10;
  8 int dcmp(double x) {
  9     if(fabs(x)<eps) return 0; else return x<0? -1:1;
 10 }
 11 
 12 struct Pt {
 13     double x,y;
 14     Pt(double x=0,double y=0):x(x),y(y) {};
 15 };
 16 typedef Pt vec;
 17 vec operator - (Pt A,Pt B) { return vec(A.x-B.x,A.y-B.y); }
 18 bool operator == (Pt A,Pt B) {
 19     return dcmp(A.x-B.x)==0 && dcmp(A.y-B.y)==0;
 20 }
 21 bool operator < (const Pt& a,const Pt& b) {
 22     return a.x<b.x || (a.x==b.x && a.y<b.y);
 23 }
 24 double Dot(vec A,vec B) { return A.x*B.x+A.y*B.y;}
 25 double cross(Pt A,Pt B) { return A.x*B.y-A.y*B.x; }
 26 
 27 bool SegIntersection(Pt a1,Pt a2,Pt b1,Pt b2) {
 28     double c1 = cross(a2-a1,b1-a1), c2 = cross(a2-a1,b2-a1),
 29              c3 = cross(b2-b1,a1-b1), c4=cross(b2-b1,a2-b1);
 30   return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;
 31 }
 32 bool OnSeg(Pt p,Pt a1,Pt a2) {
 33     return dcmp(cross(p-a1,p-a2))==0 && dcmp(Dot(p-a1,p-a2))<0;
 34 }
 35 
 36 
 37 int n;
 38 vector<Pt> ConvexHull(vector<Pt> p) {
 39     sort(p.begin(),p.end());
 40     p.erase(unique(p.begin(),p.end()),p.end());
 41     int n=p.size();
 42     int m=0;
 43     vector<Pt> ch(n+1);
 44     for(int i=0;i<n;i++) {
 45         while(m>1 && cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
 46         ch[m++]=p[i];
 47     }
 48     int k=m;
 49     for(int i=n-2;i>=0;i--) {
 50         while(m>k && cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
 51         ch[m++]=p[i];
 52     }
 53     if(n>1) m--;
 54     ch.resize(m);
 55     return ch;
 56 }
 57 
 58 int IsPointinPolygon(Pt p,vector<Pt>& poly) {
 59     int wn=0;
 60     int n=poly.size();
 61     for(int i=0;i<n;i++) {
 62         Pt& p1=poly[i];
 63         Pt& p2=poly[(i+1)%n];
 64         if(p1==p || p2==p || OnSeg(p,p1,p2)) return -1;
 65         int k=dcmp(cross(p2-p1,p-p1));
 66         int d1=dcmp(p1.y-p.y);
 67         int d2=dcmp(p2.y-p.y);
 68         if(k>0 && d1<=0 && d2>0) wn++;
 69         if(k<0 && d2<=0 && d1>0) wn--;
 70     }
 71     if(wn!=0) return 1;
 72     return 0;
 73 }
 74 bool ConvexPolygonDisjoint(vector<Pt> ch1,vector<Pt> ch2) {
 75     int c1=ch1.size() , c2=ch2.size();
 76     for(int i=0;i<c1;i++)
 77         if(IsPointinPolygon(ch1[i],ch2)!=0) return false;
 78     for(int i=0;i<c2;i++)
 79         if(IsPointinPolygon(ch2[i],ch1)!=0) return false;
 80     for(int i=0;i<c1;i++)
 81         for(int j=0;j<c2;j++)
 82             if(SegIntersection(ch1[i],ch1[(i+1)%c1],ch2[j],ch2[(j+1)%c2])) return false;
 83     return true;
 84 }
 85 
 86 int main() {
 87     int n,m;
 88     while(scanf("%d%d",&n,&m)==2 && n && m) {
 89         vector<Pt> P1,P2;
 90         double x,y;
 91         for(int i=0;i<n;i++) {
 92             scanf("%lf%lf",&x,&y);
 93             P1.push_back(Pt(x,y));
 94         }
 95         for(int i=0;i<m;i++) {
 96             scanf("%lf%lf",&x,&y);
 97             P2.push_back(Pt(x,y));
 98         }
 99         if(ConvexPolygonDisjoint(ConvexHull(P1),ConvexHull(P2)))
100             puts("Yes"); else puts("No");
101     }
102     return 0;
103 }