CodeForces 166B （凸包）

求一个多边形是否完全在另一个凸多边形内。

乍一看，好像要判点在多边形内，但复杂度不允许，仔细一想，可以把两个多边形的点混起来求一个共同的凸包，如果共同的凸包依旧是原来凸包上的点，说明是。

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stdlib.h>
  6 #include<vector>
  7 #include<cmath>
  8 #include<queue>
  9 #include<set>
 10 using namespace std;
 11 #define N 200010
 12 #define LL long long
 13 #define INF 0xfffffff
 14 const double eps = 1e-8;
 15 const double pi = acos(-1.0);
 16 const double inf = ~0u>>2;
 17 struct point
 18 {
 19     double x,y;
 20     int flag;
 21     point(double x=0,double y=0):x(x),y(y){}
 22 }p[N],ch[N],q[N];
 23 typedef point pointt;
 24 point operator -(point a,point b)
 25 {
 26     return point(a.x-b.x,a.y-b.y);
 27 }
 28 int dcmp(double x)
 29 {
 30     if(fabs(x)<eps) return 0;
 31     return x<0?-1:1;
 32 }
 33 double cross(point a,point b)
 34 {
 35     return a.x*b.y-a.y*b.x;
 36 }
 37 double mul(point a,point b,point c)
 38 {
 39     return cross(b-a,c-a);
 40 }
 41 double dis(point a)
 42 {
 43     return sqrt(a.x*a.x+a.y*a.y);
 44 }
 45 bool cmp(point a,point b)
 46 {
 47     if(mul(p[0],a,b)==0)
 48     return dis(p[0]-a)<dis(p[0]-b);
 49     return mul(p[0],a,b)>0;
 50 }
 51 int Graham(int n)
 52 {
 53     int i,k = 0,top;
 54     point tmp;
 55     for(i = 0 ; i < n; i++)
 56     {
 57         if(p[i].y<p[k].y||(p[i].y==p[k].y&&p[i].x<p[k].x))
 58             k = i;
 59     }
 60     if(k!=0)
 61     {
 62         tmp = p[0];
 63         p[0] = p[k];
 64         p[k] = tmp;
 65     }
 66     sort(p+1,p+n,cmp);
 67     ch[0] = p[0];
 68     ch[1] = p[1];
 69     top = 1;
 70     for(i = 2; i < n ; i++)
 71     {
 72         while(top>0&&dcmp(mul(ch[top-1],ch[top],p[i]))<0)
 73             top--;
 74         top++;
 75         ch[top] = p[i];
 76     }
 77     return top;
 78 }
 79 int dot_online_in(point p,point l1,point l2)
 80 {
 81     return !dcmp(mul(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps;
 82 }
 83 int main()
 84 {
 85     int n,m,i;
 86     cin>>n;
 87     for(i =0 ; i < n; i++)
 88     {
 89         scanf("%lf%lf",&p[i].x,&p[i].y);
 90         p[i].flag = 0;
 91     }
 92     cin>>m;
 93     for(i = n ; i < n+m; i++)
 94     {
 95         scanf("%lf%lf",&p[i].x,&p[i].y);
 96         p[i].flag = 1;
 97         q[i-n] = p[i];
 98     }
 99     int tn = Graham(n+m);
100     ch[tn+1] = ch[0];
101     int ff = 1;
102     for(i = 0 ; i < m ; i++)
103     {
104         if(dot_online_in(q[i],ch[tn],ch[tn+1]))
105         {
106             ff  = 0;
107             //cout<<p[i].x<<" "<<p[i].y<<endl;
108             break;
109         }
110     }
111     if(!ff)
112     {
113         puts("NO");
114         return 0;
115     }
116     for(i = 0; i <= tn ; i++)
117     if(ch[i].flag) {ff = 0;break;}
118     if(ff) puts("YES");
119     else puts("NO");
120     return 0;
121 }

View Code