uva 10256

当退化成点和线段的时候，可以不进行特判；
因为这种情况已经包括进条件1.2里面了
  1 #include <cstdio>
  2 #include <cmath>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 #define eps 1e-9
  7 using namespace std;
  8 const double pi = acos(-1);
  9 
 10 int dcmp(double x)
 11 {
 12     return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1);
 13 }
 14 
 15 struct Point
 16 {
 17     double x;
 18     double y;
 19 
 20     Point(double x = 0, double y = 0):x(x), y(y) {}
 21 
 22     bool operator < (const Point& e) const
 23     {
 24         return dcmp(x - e.x) < 0 || (dcmp(x - e.x) == 0 && dcmp(y - e.y) < 0);
 25     }
 26 
 27     bool operator == (const Point& e) const
 28     {
 29         return dcmp(x - e.x) == 0 && dcmp(y - e.y) == 0;
 30     }
 31 };
 32 
 33 typedef Point Vector;
 34 
 35 Vector operator + (Point A, Point B)
 36 {
 37     return Vector(A.x + B.x, A.y + B.y);
 38 }
 39 
 40 Vector operator - (Point A, Point B)
 41 {
 42     return Vector(A.x - B.x, A.y - B.y);
 43 }
 44 
 45 Vector operator * (Point A, double p)
 46 {
 47     return Vector(A.x * p, A.y * p);
 48 }
 49 
 50 Vector operator / (Point A, double p)
 51 {
 52     return Vector(A.x / p, A.y / p);
 53 }
 54 double dot(Point a,Point b){return a.x*b.x+a.y*b.y;}
 55 double cross(Point a,Point b){return a.x*b.y-a.y*b.x;}
 56 Point rotate(Point a,double ang){return Point(a.x*cos(ang)-a.y*sin(ang),a.x*sin(ang)+a.y*cos(ang));}
 57 int convexhull(Point *p,int n,Point *ch)
 58 {
 59     sort(p,p+n);
 60     int m=0;
 61     for(int i=0;i<n;i++)
 62     {
 63         while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
 64         ch[m++]=p[i];
 65     }
 66     int k=m;
 67     for(int i=n-2;i>=0;i--)
 68     {
 69         while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
 70         ch[m++]=p[i];
 71     }
 72     if(n>1)m--;
 73     return m;
 74 }
 75 bool onsegment(Point p,Point a,Point b)
 76 {
 77     return dcmp(cross(a-p,b-p))==0&&dcmp(dot(a-p,b-p))<0;
 78 }
 79 
 80 
 81 bool SegmentProperIntersection( Point a1, Point a2, Point b1, Point b2 )  //线段相交，交点不在端点
 82 {
 83      double c1 = cross( a2 - a1, b1 - a1 ), c2 = cross( a2 - a1, b2 - a1 ),
 84                 c3 = cross( b2 - b1, a1 - b1 ), c4 = cross( b2 - b1, a2 - b1 );
 85      return dcmp(c1)*dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
 86 }
 87 
 88 int ispointinpolygon(Point p,int n,Point *poly)
 89 {
 90     int wn=0;
 91     for(int i=0;i<n;i++)
 92     {
 93         if(onsegment(p,poly[i],poly[(i+1)%n]))return -1;
 94         int k=dcmp(cross(poly[(i+1)%n]-poly[i],p-poly[i]));
 95         int d1=dcmp(poly[i].y-p.y);
 96         int d2=dcmp(poly[(i+1)%n].y-p.y);
 97         if(k>0&&d1<=0&&d2>0)wn++;
 98         if(k<0&&d2<=0&&d1>0)wn--;
 99     }
100     if(wn!=0)return 1;
101     return 0;
102 }
103 
104 bool Check(int n,Point *ch,int m,Point *th)
105 {
106     for(int i=0;i<n;i++)
107     {
108         if(ispointinpolygon(ch[i],m,th)!=0)return 1;
109     }
110     for(int i=0;i<m;i++)
111         if(ispointinpolygon(th[i],n,ch)!=0)return 1;
112     ch[n]=ch[0];
113     th[m]=th[0];
114     for(int i=0;i<n;i++)
115         for(int j=0;j<m;j++)
116             if(SegmentProperIntersection(ch[i],ch[i+1],th[j],th[j+1]))return 1;
117     return 0;
118 }
119 
120 Point p[1009],ch[1009];
121 Point q[1009],th[1009];
122 int main()
123 {
124     int n,m;
125     while(scanf("%d%d",&n,&m)&&(n+m))
126     {
127         for(int i=0;i<n;i++)
128             scanf("%lf%lf",&p[i].x,&p[i].y);
129         for(int i=0;i<m;i++)
130             scanf("%lf%lf",&q[i].x,&q[i].y);
131         int n1=convexhull(p,n,ch);
132         int m1=convexhull(q,m,th);
133         if(Check(n1,ch,m1,th))puts("No");
134         else puts("Yes");
135     }
136     return 0;
137 }
View Code