CodeForces166BPolygons

You've got another geometrical task. You are given two non-degenerate polygons A and B as vertex coordinates. Polygon A is strictly convex. Polygon B is an arbitrary polygon without any self-intersections and self-touches. The vertices of both polygons are given in the clockwise order. For each polygon no three consecutively following vertices are located on the same straight line.

Your task is to check whether polygon B is positioned strictly inside polygon A. It means that any point of polygon B should be strictly inside polygon A. "Strictly" means that the vertex of polygon B cannot lie on the side of the polygon A.

Input

The first line contains the only integer n (3 ≤ n ≤ 10^5) — the number of vertices of polygon A. Then n lines contain pairs of integers xi, yi(|xi|, |yi| ≤ 10^9) — coordinates of the i-th vertex of polygon A. The vertices are given in the clockwise order.

The next line contains a single integer m (3 ≤ m ≤ 2·10^4) — the number of vertices of polygon B. Then following m lines contain pairs of integers xj, yj (|xj|, |yj| ≤ 10^9) — the coordinates of the j-th vertex of polygon B. The vertices are given in the clockwise order.

The coordinates of the polygon's vertices are separated by a single space. It is guaranteed that polygons A and B are non-degenerate, that polygon A is strictly convex, that polygon B has no self-intersections and self-touches and also for each polygon no three consecutively following vertices are located on the same straight line.

Output

Print on the only line the answer to the problem — if polygon B is strictly inside polygon A, print "YES", otherwise print "NO" (without the quotes).

Examples

input

-2 1

0 3

3 3

4 1

3 -2

2 -2

0 1

2 2

3 1

1 0

output

YES

input

1 2

4 2

3 -3

-2 -2

-2 1

0 1

1 2

4 1

2 -1

output

input

-1 2

2 3

4 1

3 -2

0 -3

1 0

1 1

3 1

5 -1

2 -1

output

题解

判断给定的多边形B是否在严格凸的多边形A中，有两种思路：

枚举B中所有点，判断是否都在多边形A中。
将多边形A、B的所有顶点放在一起，求凸包，判断求出来的凸包是否与原来的A一致。

思路一
由于是枚举B中所有点，且3 ≤ n ≤ 10^5、3 ≤ m ≤ 2·10^4，所以用复杂度为O(n)的点射法来判断一点是否在多边形内部肯定是不行的，由于A是严格凸的多边形，故可以考虑固定A上一点，从该点作到其他点的射线（此时相当于将A切割成了n-2个三角形），再二分查找B上一点在A中的角度区域，最后根据三角形第三边（指固定点对应的边）来判断改点是否严格在A内。当然有些情况要特判：

点在最左和最右两个三角形的非第三边上，不满足B严格包含于A。
点在中间三角形的非第三边上，满足B严格包含于A。

  1 /*******************************************************
  2                     二维几何基础
  3 【注意】数组下标从1开始。
  4 *******************************************************/
  5 
  6 #include <iostream>
  7 #include <cstdio>
  8 #include <cstdlib>
  9 #include <cmath>
 10 #include <iomanip>
 11 #include <algorithm>
 12 #include <string>
 13 #define re register
 14 #define il inline
 15 #define ll long long
 16 #define ld long double
 17 using namespace std;
 18 const ll MAXN = 1e5+5;
 19 const ll INF = 1e9;
 20 const ld EPS = 1e-9;
 21 
 22 //点坐标
 23 struct POINT
 24 {
 25     ld x, y;
 26     POINT() : x(0), y(0) {}
 27     POINT(ld _x, ld _y) : x(_x), y(_y) {}
 28 };
 29 //向量
 30 typedef POINT VECTOR;
 31 
 32 POINT xy[MAXN];     //顺时针多边形顶点存储
 33 POINT xyB[MAXN];    //判断点存储
 34 
 35 
 36 //符号函数
 37 ll sgn(ld x)    {return x < -EPS ? -1 : x > EPS;}
 38 //向量+向量=向量，点+向量=点
 39 VECTOR operator + (VECTOR a, VECTOR b)  {return {a.x+b.x,a.y+b.y};}
 40 //向量-向量=向量，点-点=向量
 41 VECTOR operator - (VECTOR a, VECTOR b)  {return {a.x-b.x,a.y-b.y};}
 42 //向量*数=向量
 43 VECTOR operator * (VECTOR a, ld k)  {return {a.x*k,a.y*k};}
 44 VECTOR operator * (ld k, VECTOR a)  {return {a.x*k,a.y*k};}
 45 //向量/数=向量
 46 VECTOR operator / (VECTOR a, ld k)  {return {a.x/k,a.y/k};}
 47 //向量==向量，点==点
 48 bool operator == (const VECTOR a, const VECTOR b)   {return !sgn(a.x-b.x) && !sgn(a.y-b.y);}
 49 //向量旋转（逆时针）
 50 VECTOR rot(VECTOR a, ld sita)   {return {a.x*cos(sita)-a.y*sin(sita),a.x*sin(sita)+a.y*cos(sita)};}
 51 //取下端点
 52 POINT min(POINT p1, POINT p2)   {return p1.y<p2.y ? p1:p2;}
 53 //取上端点
 54 POINT max(POINT p1, POINT p2)   {return p1.y<p2.y ? p2:p1;}
 55 //点积
 56 ld dot(POINT p1, POINT p2, POINT p) {return (p.x-p1.x)*(p2.x-p1.x)+(p.y-p1.y)*(p2.y-p1.y);} //（三点式：共p1端点）
 57 ld dot(VECTOR a, VECTOR b)      {return a.x*b.x+a.y*b.y;}   //向量式
 58 //叉积
 59 ld cross(POINT p1, POINT p2, POINT p)   {return (p.x-p1.x)*(p2.y-p1.y)-(p.y-p1.y)*(p2.x-p1.x);} //（三点式：共p1端点）
 60 ld cross(VECTOR a, VECTOR b)    {return a.x*b.y-a.y*b.x;}   //向量式（aXb）
 61 //向量长度
 62 ld vlen(VECTOR a) {return sqrt(dot(a,a));}
 63 //向量夹角余弦值
 64 ld vcos(VECTOR a, VECTOR b) {return dot(a,b)/(vlen(a)*vlen(b));}
 65 //向量夹角正弦值
 66 ld vsin(VECTOR a, VECTOR b) {return fabs(cross(a,b))/(vlen(a)*vlen(b));}
 67 //求直线斜率【注意】确保斜率存在
 68 ld slope(VECTOR a)  {return a.y/a.x;}   //向量式
 69 ld slope(POINT p, POINT q)  {return (p.y-q.y)/(p.x-q.x);}   //两点式
 70 //单位向量【注意】确保非零向量
 71 VECTOR norm(VECTOR a)   {return a/vlen(a);}
 72 //两直线交点
 73 POINT intersectline(POINT p, VECTOR v, POINT q, VECTOR w)   {return p+v*cross(w,p-q)/cross(v,w);}   //（参数式：P=P0+t*v，P0为直线上某一点，v为直线的方向向量）
 74 //点在直线上的投影
 75 POINT proline(POINT a, POINT b, POINT p)    {return a+(b-a)*(dot(b-a,p-a)/dot(b-a,b-a));}
 76 //点关于直线的对称点
 77 POINT refline(POINT a, POINT b, POINT p)    {return proline(a,b,p)*2-p;}
 78 //判断两直线是否平行
 79 bool parallel(POINT p1, POINT p2, POINT q1, POINT q2)   {return !sgn(cross(p2-p1,q2-q1)) && sgn(cross(p1-q1,p2-q1));}
 80 //判断两直线重合
 81 bool superposition(POINT p1, POINT p2, POINT q1, POINT q2)  {return !sgn(cross(p2-p1,q2-q1)) && !sgn(cross(p1-q1,p2-q1));}
 82 //点到直线距离
 83 ld disline(POINT a, POINT b, POINT p)   {return fabs(cross(b-a,p-a))/vlen(b-a);}    //不取绝对值得到的是有向距离
 84 //点到线段距离（两种情况：点的投影在线段上，则为垂直距离；点的投影不在线段上，则为到两端距离的最小值）
 85 ld disseg(POINT a, POINT b, POINT p)    {return a==b ? vlen(p-a):dot(b-a,p-a)<0 ? vlen(p-a):dot(b-a,p-b)>0 ? vlen(p-b):fabs(cross(b-a,p-a))/vlen(b-a);}
 86 //线段相交判断（严格）
 87 bool intersectseg(POINT p1, POINT p2, POINT q1, POINT q2)   {return cross(p1-q1,q2-q1)*cross(p2-q1,q2-q1)<0 && cross(q1-p1,p2-p1)*cross(q2-p1,p2-p1)<0;}
 88 //判断点p(x,y)是否在线段p1p2上（两种情况：1.包括端点；2.不包含端点）
 89 bool onseg(POINT p1, POINT p2, POINT p) {return !sgn(cross(p1,p2,p)) && sgn(dot(p,p1,p2))<=0;}  //包含端点
 90 bool onseg_strict(POINT p1, POINT p2, POINT p)  {return !sgn(cross(p1,p2,p)) && sgn(dot(p,p1,p2))<0;}   //不包含端点
 91 
 92 //点射法判断点是否在多边形内部（边界也算在内部）
 93 //复杂度O(n)（不论凹凸）
 94 bool inpolygon_dot(ld x, ld y, ll n)
 95 {
 96     ll cnt = 0;
 97     for(re ll i = 0; i < n; ++i)
 98     {
 99         POINT p1 = min(xy[i+1], xy[(i+1)%n+1]);    //取下端点
100         POINT p2 = max(xy[i+1], xy[(i+1)%n+1]);    //取上端点
101         //特判点在线段上
102         if(onseg(p1,p2,{x,y}))    return true;
103         //从点(x,y)向x反方向引出射线
104         //计算点射到的多边形的边数边数
105         if(sgn(p1.y-y)<0 && sgn(y-p2.y) <=0 && sgn(cross(p1,p2,{x,y}))>0)   ++cnt;
106     }
107     if(cnt%2)   return true;
108     else    return false;
109 }
110 
111 //二分法判断点是否在多边形内部（不包括边界）
112 //复杂度O(logn)（要求凸多边形）
113 bool inpolygon_bis(ld x, ld y, ll n)
114 {
115     POINT p = {x,y};
116     ll l = 2, r = n;
117     //判断是否在幅角最小和最大的两条边上
118     if(onseg(xy[1],xy[l],p) || onseg(xy[1],xy[n],p))    return false;
119     //二分法判断是否在多边形内部
120     while(l < r)
121     {
122         ll mid = (l+r)>>1;  //【注意】如此取中点最终：r==l或r==l-1（只有此两种情况）
123         ll d = sgn(cross(xy[mid]-xy[1],p-xy[1]));
124         if(d < 0)   l = mid+1;
125         else if(d > 0)  r = mid-1;
126         else
127         {
128             if(onseg_strict(xy[1],xy[mid],p))
129             {
130                 return true;
131             }
132             else
133             {
134                 return false;
135             }
136         }
137     }
138     //判断在最终二分得到的对角线两端的边是否都满足严格在内的条件
139     if(l >= r && (sgn(cross(xy[l]-xy[l-1],p-xy[l-1]))>=0 || sgn(cross(xy[l%n+1]-xy[l],p-xy[l]))>=0))
140     {
141         return false;
142     }
143     return true;
144 }
145 
146 //计算多边形面积（凹凸均可）
147 ld polygonarea(ll n)
148 {
149     ld aera = 0;
150     for(re ll i = 0; i < n; ++i)
151     {
152         aera += cross(xy[i+1], xy[(i+1)%n+1]);
153     }
154     //计算出来的aera为有向面积
155     return fabs(aera)/2;
156 }
157 
158 int main()
159 {
160     std::ios::sync_with_stdio(false);
161     //判断点是否在多边形内（不包括边界）
162     ll n;
163     std::cin >> n;
164     for(re ll i = 1; i <= n; ++i)
165     {
166         std::cin >> xy[i].x;
167         std::cin >> xy[i].y;
168     }
169     ll m;
170     cin >> m;
171     for(re ll i = 1; i <= m; ++i)
172     {
173         cin >> xyB[i].x;
174         cin >> xyB[i].y;
175     }
176     for(re ll i = 1; i <= m; ++i)
177     {
178         if(!inpolygon_bis(xyB[i].x, xyB[i].y, n))
179         {
180             printf("NO\n");
181             return 0;
182         }
183     }
184     printf("YES\n");
185     return 0;
186 }

View Code

思路二
将A、B所有顶点加在一起，利用graham算法或andrew算法求出凸包，判断是否和A相等即可。

  1 /************************************************************************
  2                             Graham算法
  3 时间复杂度：O(nlogn)。Scan过程为O(n)，预处理排序为O(nlogn)。
  4 预处理排序：极角排序。
  5 【注意】数组下标从1开始。
  6 ************************************************************************/
  7 
  8 
  9 /*
 10 思想：
 11 把所有点放在二维坐标系中，则纵坐标最小的点一定是凸包上的点，记为xy0。计算
 12 各个点相对xy0的幅角，按从小到大的顺序对各个点排序。（当幅角相同是，距离xy0
 13 比较近的排在前面）则幅角最小的点和最大的点一定在凸包上，且第一个点即为xy0。
 14 取幅角最小的点xy[j]，将xy0、xy[j]入栈。连接栈顶的点和次栈顶的点，得到直线l，
 15 看当前点是在直线的右边还是左边，在右边则栈顶元素不是凸包上的点，将其弹出，
 16 返回继续执行。如果在左边，则当前点是凸包上的点。一直到幅角最大的那个点为之。
 17 分析：
 18 两个向量的叉积P1xP2 = x1*y2 - x2*y1，其中用结果的正负代表叉乘结果的方向。
 19 该公式本质是两个三维向量（z轴分量为0）叉乘的结果（原来结果为(x1*y2 - x2*y1)
 20 *k，其中k是z轴单位向量）。
 21 */
 22 
 23 
 24 #include <bits/stdc++.h>
 25 #include <stack>
 26 #include <cstdio>
 27 #include <cmath>
 28 #include <algorithm>
 29 #define re register
 30 #define il inline
 31 #define ll long long
 32 #define ld long double
 33 using namespace std;
 34 
 35 const ll MAXN = 5e5+5;
 36 const ld INF = 1e9;
 37 const ld EPS = 1e-9;
 38 
 39 //点坐标
 40 struct POINT
 41 {
 42     ld x, y;
 43     POINT() : x(0), y(0) {}
 44     POINT(ld _x, ld _y) : x(_x), y(_y) {}
 45 };
 46 //向量
 47 typedef POINT VECTOR;
 48 
 49 ll vexcnt = 0;      //凸包顶点数
 50 POINT xy0;          //先纵坐标后横坐标最小的点
 51 POINT xy[MAXN], xyt[MAXN];     //多边形顶点存储，临时多边形顶点存储
 52 POINT convex[MAXN]; //凸包顶点数组
 53 
 54 
 55 //符号函数
 56 ll sgn(ld x)    {return x < -EPS ? -1 : x > EPS;}
 57 //向量+向量=向量，点+向量=点
 58 VECTOR operator + (VECTOR a, VECTOR b)  {return {a.x+b.x,a.y+b.y};}
 59 //向量-向量=向量，点-点=向量
 60 VECTOR operator - (VECTOR a, VECTOR b)  {return {a.x-b.x,a.y-b.y};}
 61 //向量*数=向量
 62 VECTOR operator * (VECTOR a, ld k)  {return {a.x*k,a.y*k};}
 63 VECTOR operator * (ld k, VECTOR a)  {return {a.x*k,a.y*k};}
 64 //向量/数=向量
 65 VECTOR operator / (VECTOR a, ld k)  {return {a.x/k,a.y/k};}
 66 //向量==向量，点==点
 67 bool operator == (const VECTOR a, const VECTOR b)   {return !sgn(a.x-b.x) && !sgn(a.y-b.y);}
 68 //向量偏序关系（先y轴再x轴）
 69 bool operator < (const VECTOR a, const VECTOR b)    {return !sgn(a.y-b.y) ? a.x < b.x : a.y < b.y;}
 70 //向量旋转（逆时针）
 71 VECTOR rot(VECTOR a, ld sita)   {return {a.x*cos(sita)-a.y*sin(sita),a.x*sin(sita)+a.y*cos(sita)};}
 72 //取下端点
 73 POINT min(POINT p1, POINT p2)   {return p1.y<p2.y ? p1:p2;}
 74 //取上端点
 75 POINT max(POINT p1, POINT p2)   {return p1.y<p2.y ? p2:p1;}
 76 //点积
 77 ld dot(POINT p1, POINT p2, POINT p) {return (p.x-p1.x)*(p2.x-p1.x)+(p.y-p1.y)*(p2.y-p1.y);} //（三点式：共p1端点）
 78 ld dot(VECTOR a, VECTOR b)      {return a.x*b.x+a.y*b.y;}   //向量式
 79 //叉积
 80 ld cross(POINT p1, POINT p2, POINT p)   {return (p.x-p1.x)*(p2.y-p1.y)-(p.y-p1.y)*(p2.x-p1.x);} //（三点式：共p1端点）
 81 ld cross(VECTOR a, VECTOR b)    {return a.x*b.y-a.y*b.x;}   //向量式（aXb）
 82 //向量长度
 83 ld vlen(VECTOR a) {return sqrt(dot(a,a));}
 84 //向量夹角余弦值
 85 ld vcos(VECTOR a, VECTOR b) {return dot(a,b)/(vlen(a)*vlen(b));}
 86 //向量夹角正弦值
 87 ld vsin(VECTOR a, VECTOR b) {return fabs(cross(a,b))/(vlen(a)*vlen(b));}
 88 //极角排序（从小到大，极角相同则距离初始点由近到远）
 89 bool cmppas(const POINT p1, const POINT p2) {return !sgn(cross(p1-xy0,p2-xy0)) ? vlen(p1-xy0)<vlen(p2-xy0):sgn(cross(p1-xy0,p2-xy0))>0;}
 90 //距离排序（从小到大，距离初始点的距离）
 91 bool cmpdisup(const POINT p1, const POINT p2) {return vlen(p1-xy0)<vlen(p2-xy0);}
 92 //距离排序（从大到小，距离初始点的距离）
 93 bool cmpdisdown(const POINT p1, const POINT p2) {return vlen(p1-xy0)>vlen(p2-xy0);}
 94 //求凸包周长
 95 ld convexperimeter()
 96 {
 97     ld ans = 0;
 98     for(re ll i = 1; i <= vexcnt; ++i)
 99     {
100         ans += vlen(convex[i]-convex[i%vexcnt+1]);
101     }
102     return ans;
103 }
104 //计算多边形面积
105 ld polygonarea()
106 {
107     ld aera = 0;
108     for(re ll i = 0; i < vexcnt; ++i)
109     {
110         aera += cross(convex[i+1], convex[(i+1)%vexcnt+1]);
111     }
112     return fabs(aera)/2;        //不加绝对值为有向面积
113 }
114 
115 //graham算法求凸包（凸包数组正序为逆时针）
116 //1.严格凸包（没有重复点和三点共线）2.非严格凸包（允许重复点和三点共线）
117 void graham(ll n)
118 {
119     memcpy(xyt,xy,sizeof(xy));          //备份原来顶点集
120     sort(xyt+1,xyt+n+1,cmppas);         //第一位一定为xy0（由极角排序规则可知）
121     //使极角最小和最大的点按照到初始点距离有序排序（便于后续划分严格凸包和非严格凸包）
122     ll first = 0, firstcnt = 0;         //first记录幅角最小的点
123     while(xyt[++first]==xyt[1]);
124     for(re ll i = first; i <= n; ++i)
125     {
126         if(!sgn(cross(xyt[i]-xyt[1],xyt[first]-xyt[1])))    ++firstcnt;
127         else    break;
128     }
129     sort(xyt+first,xyt+first+firstcnt,cmpdisup);
130     ll last = n, lastcnt = 0;           //last记录幅角最大的点
131     for(re ll i = last; i >= 1; --i)
132     {
133         if(!sgn(cross(xyt[i]-xyt[1],xyt[last]-xyt[1]))) ++lastcnt;
134         else    break;
135     }
136     last -= lastcnt-1;
137     sort(xyt+last,xyt+last+lastcnt,cmpdisdown);
138     //求解凸包顶点集
139     convex[++vexcnt] = xyt[1];            //xyt[1]一定在凸包中
140     ll j = 2;
141     while(j <= n)
142     {
143         if(vexcnt <= 1)                 //因为xyt[2]不一定在凸包集中（对于严格凸包来说）
144         {
145             convex[++vexcnt] = xyt[j++];
146         }
147         else
148         {
149             //取前面两个点
150             //严格凸包：sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[j]-convex[vexcnt]))>0
151             //非严格凸包：sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[j]-convex[vexcnt]))>=0
152             if(sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[j]-convex[vexcnt]))>=0)  convex[++vexcnt] = xyt[j++];
153             else    --vexcnt;
154         }
155     }
156     //for(re ll i = 1; i <= vexcnt; ++i)    cout << "(" << convex[i].x << "," << convex[i].y << ")" << endl;
157     return;
158 }
159 
160 int main()
161 {
162     std::ios::sync_with_stdio(false);
163     xy0.x = xy0.y = INF;              //初始化第一个点
164     ll n;
165     cin >> n;
166     for(re ll i = 1; i <= n; ++i)
167     {
168         cin >> xy[i].x >> xy[i].y;
169         if(xy[i] < xy0)
170         {
171             xy0 = xy[i];
172         }
173     }
174     ll m;
175     cin >> m;
176     for(re ll i = n+1; i <= n+m; ++i)
177     {
178         cin >> xy[i].x >> xy[i].y;
179         if(xy[i] < xy0)
180         {
181             xy0 = xy[i];
182         }
183     }
184     graham(n+m);
185     //判断点是否全部在凸包内
186     if(vexcnt != n)
187     {
188         printf("NO\n");
189         return 0;
190     }
191     ll record = -1;
192     for(re ll i = 1; i <= n; ++i)
193     {
194         if(convex[i] == xy[1])
195         {
196             record = i;
197             break;
198         }
199     }
200     if(record == -1)
201     {
202         printf("NO\n");
203         return 0;
204     }
205     for(re ll i = 1; i <= n; ++i, record=record<=1 ? n:record-1)
206     {
207         if(!(convex[record] == xy[i]))
208         {
209             printf("NO\n");
210             return 0;
211         }
212     }
213     printf("YES\n");
214     return 0;
215 }

View Code

  1 /************************************************************************
  2                     Andrew算法（Graham算法变种）
  3 时间复杂度：O(nlogn)。Scan过程为O(n)，预处理排序为O(nlogn)。
  4 预处理排序：水平排序排序。
  5 【注意】数组下标从1开始。
  6 ************************************************************************/
  7 
  8 
  9 /*
 10 思想：
 11 预处理排序改为水平排序，按照横坐标从小到大进行排序，横坐标相同则按纵坐标从
 12 小到大排。按照graham算法思想从p1、p2扫描所有点得到下凸包，再从pn、pn-1扫
 13 描所有点得到上凸包，二者结合即为整个凸包。（注意：这里的p2不一定在凸包里）
 14 分析：
 15 两个向量的叉积P1xP2 = x1*y2 - x2*y1，其中用结果的正负代表叉乘结果的方向。
 16 该公式本质是两个三维向量（z轴分量为0）叉乘的结果（原来结果为(x1*y2 - x2*y1)
 17 *k，其中k是z轴单位向量）。
 18 */
 19 
 20 
 21 #include <bits/stdc++.h>
 22 #include <stack>
 23 #include <cstdio>
 24 #include <cmath>
 25 #include <algorithm>
 26 #define re register
 27 #define il inline
 28 #define ll long long
 29 #define ld long double
 30 using namespace std;
 31 
 32 const ll MAXN = 5e5+5;
 33 const ld INF = 1e9;
 34 const ld EPS = 1e-9;
 35 
 36 //点坐标
 37 struct POINT
 38 {
 39     ld x, y;
 40     POINT() : x(0), y(0) {}
 41     POINT(ld _x, ld _y) : x(_x), y(_y) {}
 42 };
 43 //向量
 44 typedef POINT VECTOR;
 45 
 46 ll vexcnt = 0;      //凸包顶点数
 47 POINT xy[MAXN], xyt[MAXN];     //多边形顶点存储，临时多边形顶点存储
 48 POINT convex[MAXN]; //凸包顶点数组
 49 
 50 
 51 //符号函数
 52 ll sgn(ld x)    {return x < -EPS ? -1 : x > EPS;}
 53 //向量+向量=向量，点+向量=点
 54 VECTOR operator + (VECTOR a, VECTOR b)  {return {a.x+b.x,a.y+b.y};}
 55 //向量-向量=向量，点-点=向量
 56 VECTOR operator - (VECTOR a, VECTOR b)  {return {a.x-b.x,a.y-b.y};}
 57 //向量*数=向量
 58 VECTOR operator * (VECTOR a, ld k)  {return {a.x*k,a.y*k};}
 59 VECTOR operator * (ld k, VECTOR a)  {return {a.x*k,a.y*k};}
 60 //向量/数=向量
 61 VECTOR operator / (VECTOR a, ld k)  {return {a.x/k,a.y/k};}
 62 //向量==向量，点==点
 63 bool operator == (const VECTOR a, const VECTOR b)   {return !sgn(a.x-b.x) && !sgn(a.y-b.y);}
 64 //向量偏序关系（先x轴再y轴）
 65 bool operator < (const VECTOR a, const VECTOR b)    {return !sgn(a.x-b.x) ? a.y < b.y : a.x < b.x;}
 66 //向量旋转（逆时针）
 67 VECTOR rot(VECTOR a, ld sita)   {return {a.x*cos(sita)-a.y*sin(sita),a.x*sin(sita)+a.y*cos(sita)};}
 68 //取下端点
 69 POINT min(POINT p1, POINT p2)   {return p1.y<p2.y ? p1:p2;}
 70 //取上端点
 71 POINT max(POINT p1, POINT p2)   {return p1.y<p2.y ? p2:p1;}
 72 //点积
 73 ld dot(POINT p1, POINT p2, POINT p) {return (p.x-p1.x)*(p2.x-p1.x)+(p.y-p1.y)*(p2.y-p1.y);} //（三点式：共p1端点）
 74 ld dot(VECTOR a, VECTOR b)      {return a.x*b.x+a.y*b.y;}   //向量式
 75 //叉积
 76 ld cross(POINT p1, POINT p2, POINT p)   {return (p.x-p1.x)*(p2.y-p1.y)-(p.y-p1.y)*(p2.x-p1.x);} //（三点式：共p1端点）
 77 ld cross(VECTOR a, VECTOR b)    {return a.x*b.y-a.y*b.x;}   //向量式（aXb）
 78 //向量长度
 79 ld vlen(VECTOR a) {return sqrt(dot(a,a));}
 80 //向量夹角余弦值
 81 ld vcos(VECTOR a, VECTOR b) {return dot(a,b)/(vlen(a)*vlen(b));}
 82 //向量夹角正弦值
 83 ld vsin(VECTOR a, VECTOR b) {return fabs(cross(a,b))/(vlen(a)*vlen(b));}
 84 //求凸包周长
 85 ld convexperimeter()
 86 {
 87     ld ans = 0;
 88     for(re ll i = 1; i <= vexcnt; ++i)
 89     {
 90         ans += vlen(convex[i]-convex[i%vexcnt+1]);
 91     }
 92     return ans;
 93 }
 94 //计算多边形面积
 95 ld polygonarea()
 96 {
 97     ld aera = 0;
 98     for(re ll i = 0; i < vexcnt; ++i)
 99     {
100         aera += cross(convex[i+1], convex[(i+1)%vexcnt+1]);
101     }
102     return fabs(aera)/2;        //不加绝对值为有向面积
103 }
104 
105 //andrew算法求凸包（凸包数组正序为逆时针）
106 //1.严格凸包（没有重复点和三点共线）2.非严格凸包（允许重复点和三点共线）
107 void andrew(ll n)
108 {
109     memcpy(xyt,xy,sizeof(xy));          //备份原来顶点集
110     sort(xyt+1,xyt+n+1);                //排序后xyt[1]和xyt[n]一定在凸包中
111     //求解凸包顶点集
112     //正向扫描（下凸包）
113     convex[++vexcnt] = xyt[1];          //xyt[1]一定在凸包中
114     ll j = 2;
115     while(j <= n)
116     {
117         if(vexcnt <= 1)                 //因为xyt[2]不一定在凸包集中
118         {
119             convex[++vexcnt] = xyt[j++];
120         }
121         else
122         {
123             //取前面两个点
124             //严格凸包：sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[j]-convex[vexcnt]))>0
125             //非严格凸包：sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[j]-convex[vexcnt]))>=0
126             if(sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[j]-convex[vexcnt]))>=0)  convex[++vexcnt] = xyt[j++];
127             else    --vexcnt;
128         }
129     }
130     //反向扫描（上凸包）
131     //至少包含了xyt[1]和xyt[n]
132     ll k = n-1;
133     while(k >= 1)
134     {
135         //取前面两个点
136         //严格凸包：sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[k]-convex[vexcnt]))>0
137         //非严格凸包：sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[k]-convex[vexcnt]))>=0
138         if(sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[k]-convex[vexcnt]))>=0)  convex[++vexcnt] = xyt[k--];
139         else    --vexcnt;
140     }
141     while(convex[--vexcnt]==convex[1]);     //因为和xyt[1]相等的点都在下凸包中了
142     for(re ll i = 1; i <= vexcnt; ++i)    cout << "(" << convex[i].x << "," << convex[i].y << ")" << endl;
143     return;
144 }
145 
146 int main()
147 {
148     std::ios::sync_with_stdio(false);
149     ll n;
150     cin >> n;
151     for(re ll i = 1; i <= n; ++i)
152     {
153         cin >> xy[i].x >> xy[i].y;
154     }
155     ll m;
156     cin >> m;
157     for(re ll i = n+1; i <= n+m; ++i)
158     {
159         cin >> xy[i].x >> xy[i].y;
160     }
161     andrew(n+m);
162     //判断点是否全部在凸包内
163     if(vexcnt != n)
164     {
165         printf("NO\n");
166         return 0;
167     }
168     ll record = -1;
169     for(re ll i = 1; i <= n; ++i)
170     {
171         if(convex[i] == xy[1])
172         {
173             record = i;
174             break;
175         }
176     }
177     if(record == -1)
178     {
179         printf("NO\n");
180         return 0;
181     }
182     for(re ll i = 1; i <= n; ++i, record=record<=1 ? n:record-1)
183     {
184         if(!(convex[record] == xy[i]))
185         {
186             printf("NO\n");
187             return 0;
188         }
189     }
190     printf("YES\n");
191     return 0;
192 }

View Code