#include <bits/stdc++.h>
using namespace std;
namespace Geometric {
const double eps = 1e-8, Pi = acos(-1);
inline int dcmp(double x) { return ((x > eps) - (x < -eps)); }
struct Point {
  double x, y;
  Point(double X = 0, double Y = 0) : x(X), y(Y) {}
  void In() { scanf("%lf%lf", &x, &y); }
  void Out() { printf("%.2lf %.2lf\n", x, y); }
  friend Point operator+(Point a, Point b) {
    return Point(a.x + b.x, a.y + b.y);
  }
  friend Point operator-(Point a, Point b) {
    return Point(a.x - b.x, a.y - b.y);
  }
  friend Point operator*(Point a, double k) { return Point(k * a.x, k * a.y); }
  friend double operator*(Point a, Point b) { return a.x * b.y - a.y * b.x; };
  friend double operator^(Point a, Point b) { return a.x * b.x + a.y * b.y; };
  friend int operator==(Point a, Point b) {
    return !dcmp(a.x - b.x) && !dcmp(a.y - b.y);
  }
  friend int operator<(Point a, Point b) {
    return dcmp(a.x - b.x) < 0 || (dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) < 0);
  }
  double Len() { return sqrt(x * x + y * y); }
  Point Normal() { return Point(-y, x); }
  double Polar_Angle(Point v) { return atan2(v.y, v.x); }
};
double Angel(Point a, Point b) { return acos(a * b / a.Len() / b.Len()); }
Point Point_Rotate_Around_Point(Point a, Point b, double k) {
  double x = (a.x - b.x) * cos(k) + (a.y - b.y) * sin(k) + b.x;
  double y = -(a.x - b.x) * sin(k) + (a.y - b.y) * cos(k) + b.y;
  return Point(x, y);
}
struct Line {
  Point p0, a, b;
  Point v;
  void Get_Expression() {
    v = a - b;
    if (dcmp(v.x - 0)) {
      v = v * (1.0 / v.x);
      p0 = a - v * (a.x / v.x);
    } else
      p0 = a;
  }
  void In() {
    a.In();
    b.In();
    Get_Expression();
  }
  Line() {}
  Line(Point A_, Point B_) : a(A_), b(B_) { Get_Expression(); }
  Point Get_Point_In_Line(double x) { return p0 + v * x; }
};
int Is_Point_In_Line(Point p, Line l) { return !dcmp((p - l.a) * (l.b - l.a)); }
int Is_Point_In_Segment(Point p, Line l) {
  return !dcmp((p - l.a) * (l.b - l.a)) && dcmp((p - l.a) ^ (p - l.b)) <= 0;
}
double Distance_Point_To_Line(Point p, Line l) {
  Point v1 = l.b - l.a, v2 = p - l.a;
  return fabs(v1 * v2 / v1.Len());
}
double Distance_Point_To_Segment(Point p, Line l) {
  if (l.a == l.b) return (p - l.a).Len();
  Point v1 = p - l.a, v2 = p - l.b, v3 = l.b - l.a;
  if (dcmp(v1 ^ v3) < 0) return v1.Len();
  if (dcmp(v2 ^ v3) > 0) return v2.Len();
  return fabs(v1 * v3 / v3.Len());
}
Point Foot_Point_To_line(Point p, Line l) {
  Point v1 = p - l.a, v2 = p - l.b, v3 = l.b - l.a;
  double len1 = (v1 ^ v3) / v3.Len(), len2 = -1.0 * (v2 ^ v3) / v3.Len();
  return l.a + v3 * (len1 / (len1 + len2));
}
Point Symmetric_Point_About_Line(Point p, Line l) {
  return p + (Foot_Point_To_line(p, l) - p) * 2;
}
Point Line_Line_Cross_Point(Line l1, Line l2) {
  Point v1 = l1.b - l1.a, v2 = l2.b - l2.a, v3 = l1.a - l2.a;
  return l1.a + v1 * ((v2 * v3) / (v1 * v2));
}
int Is_Line_Line_Cross(Line l1, Line l2) {
  return Is_Point_In_Segment(Line_Line_Cross_Point(l1, l2), l2);
}
int Is_Segment_Segment_Cross(Line l1, Line l2) {
  double c1 = (l1.b - l1.a) * (l2.a - l1.a), c2 = (l1.b - l1.a) * (l2.b - l1.a);
  double d1 = (l2.b - l2.a) * (l1.a - l2.a), d2 = (l2.b - l2.a) * (l1.b - l2.a);
  return dcmp(c1) * dcmp(c2) <= 0 && dcmp(d1) * dcmp(d2) <= 0;
};
struct Polygon {
  int n;
  vector<Point> point;
  Polygon(int N = 0) {
    n = N;
    point.clear();
  }
  void clear() {
    n = 0;
    point.clear();
  }
  void Insert(Point p) {
    point.push_back(p);
    ++n;
  }
  Point Gravity_Center() {
    Point re;
    for (int i = 0; i < n; ++i) re.x += point[i].x, re.y += point[i].y;
    return re * (1.0 / n);
  }
  double Area() {
    double re = 0;
    for (int i = 1; i < n - 1; ++i)
      re += (point[i] - point[0]) * (point[i + 1] - point[0]);
    return re / 2.0;
  }
};
int Is_Point_In_Polygon(Point p, Polygon &ply) {
  int cnt = 0;
  double tmp;
  for (int i = 0; i < ply.n; ++i) {
    int j = i < ply.n - 1 ? i + 1 : 0;
    if (Is_Point_In_Segment(p, Line(ply.point[i], ply.point[j]))) return 2;
    if (dcmp(p.y - min(ply.point[i].y, ply.point[j].y)) >= 0 &&
        dcmp(p.y - max(ply.point[i].y, ply.point[j].y)) < 0) {
      tmp = ply.point[i].x + (p.y - ply.point[i].y) /
                                 (ply.point[j].y - ply.point[i].y) *
                                 (ply.point[j].x - ply.point[i].x);
      cnt += (dcmp(tmp - p.x) > 0);
    }
  }
  return cnt & 1;
}
int Is_Point_In_Polygon_(Point p, Polygon &ply) {
  if (dcmp((p - ply.point[0]) * (ply.point[1] - ply.point[0])) > 0 ||
      dcmp((ply.point[ply.n - 1] - ply.point[0]) * (p - ply.point[0])) > 0)
    return 0;
  if (Is_Point_In_Segment(p, Line(ply.point[0], ply.point[1])) ||
      Is_Point_In_Segment(p, Line(ply.point[0], ply.point[ply.n - 1])))
    return 2;
  int l = 1, r = ply.n - 2, mid;
  while (l < r) {
    mid = (l + r + 1) >> 1;
    if (dcmp((ply.point[mid] - ply.point[0]) * (p - ply.point[0])) > 0)
      l = mid;
    else
      r = mid - 1;
  }
  if (dcmp((p - ply.point[l]) * (ply.point[l + 1] - ply.point[l])) > 0)
    return 0;
  if (Is_Point_In_Segment(p, Line(ply.point[l], ply.point[l + 1]))) return 2;
  return 1;
}
Polygon Andrew_Convex_Hull(Polygon &ply) {
  Polygon re;
  sort(ply.point.begin(), ply.point.end());
  int cnt = -1;
  for (int i = 0; i < ply.n; ++i) {
    while (cnt > 0 && dcmp((re.point[cnt] - re.point[cnt - 1]) *
                           (ply.point[i] - re.point[cnt - 1])) < 0)
      cnt--;
    ++cnt;
    if (cnt < re.point.size())
      re.point[cnt] = ply.point[i];
    else
      re.Insert(ply.point[i]);
  }
  int tmp = cnt;
  for (int i = ply.n - 2; i >= 0; --i) {
    while (cnt > tmp && dcmp((re.point[cnt] - re.point[cnt - 1]) *
                             (ply.point[i] - re.point[cnt - 1])) < 0)
      cnt--;
    ++cnt;
    if (cnt < re.point.size())
      re.point[cnt] = ply.point[i];
    else
      re.Insert(ply.point[i]);
  }
  re.n = 0;
  for (vector<Point>::iterator it = re.point.begin(); it != re.point.end();) {
    if (re.n < cnt) {
      ++re.n;
      ++it;
    } else
      it = re.point.erase(it);
  }
  return re;
}
struct Circle {};
};  // namespace Geometric
using namespace Geometric;
const int N = 1e5 + 7, M = 2e4 + 7;
int n, m;
Polygon ply, re;
Point p, pb[M];
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    p.In();
    ply.Insert(p);
  }
  cin >> m;
  for (int i = 1; i <= m; i++) {
    pb[i].In();
    ply.Insert(pb[i]);
  }
  sort(pb + 1, pb + 1 + m);
  re = Andrew_Convex_Hull(ply);
  int flag = 1;
  for (int i = 0; i < re.n; i++) {
    int t = lower_bound(pb + 1, pb + 1 + m, re.point[i]) - pb;
    if (pb[t] == re.point[i]) {
      flag = 0;
      break;
    }
  }
  if (flag)
    cout << "YES";
  else
    cout << "NO";
}

### Prompt

Create a solution in cpp for the following problem:

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 ≤ 105) — the number of vertices of polygon A. Then n lines contain pairs of integers xi, yi (|xi|, |yi| ≤ 109) — 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·104) — the number of vertices of polygon B. Then following m lines contain pairs of integers xj, yj (|xj|, |yj| ≤ 109) — 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

6
-2 1
0 3
3 3
4 1
3 -2
2 -2
4
0 1
2 2
3 1
1 0


Output

YES


Input

5
1 2
4 2
3 -3
-2 -2
-2 1
4
0 1
1 2
4 1
2 -1


Output

NO


Input

5
-1 2
2 3
4 1
3 -2
0 -3
5
1 0
1 1
3 1
5 -1
2 -1


Output

NO

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
namespace Geometric {
const double eps = 1e-8, Pi = acos(-1);
inline int dcmp(double x) { return ((x > eps) - (x < -eps)); }
struct Point {
  double x, y;
  Point(double X = 0, double Y = 0) : x(X), y(Y) {}
  void In() { scanf("%lf%lf", &x, &y); }
  void Out() { printf("%.2lf %.2lf\n", x, y); }
  friend Point operator+(Point a, Point b) {
    return Point(a.x + b.x, a.y + b.y);
  }
  friend Point operator-(Point a, Point b) {
    return Point(a.x - b.x, a.y - b.y);
  }
  friend Point operator*(Point a, double k) { return Point(k * a.x, k * a.y); }
  friend double operator*(Point a, Point b) { return a.x * b.y - a.y * b.x; };
  friend double operator^(Point a, Point b) { return a.x * b.x + a.y * b.y; };
  friend int operator==(Point a, Point b) {
    return !dcmp(a.x - b.x) && !dcmp(a.y - b.y);
  }
  friend int operator<(Point a, Point b) {
    return dcmp(a.x - b.x) < 0 || (dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) < 0);
  }
  double Len() { return sqrt(x * x + y * y); }
  Point Normal() { return Point(-y, x); }
  double Polar_Angle(Point v) { return atan2(v.y, v.x); }
};
double Angel(Point a, Point b) { return acos(a * b / a.Len() / b.Len()); }
Point Point_Rotate_Around_Point(Point a, Point b, double k) {
  double x = (a.x - b.x) * cos(k) + (a.y - b.y) * sin(k) + b.x;
  double y = -(a.x - b.x) * sin(k) + (a.y - b.y) * cos(k) + b.y;
  return Point(x, y);
}
struct Line {
  Point p0, a, b;
  Point v;
  void Get_Expression() {
    v = a - b;
    if (dcmp(v.x - 0)) {
      v = v * (1.0 / v.x);
      p0 = a - v * (a.x / v.x);
    } else
      p0 = a;
  }
  void In() {
    a.In();
    b.In();
    Get_Expression();
  }
  Line() {}
  Line(Point A_, Point B_) : a(A_), b(B_) { Get_Expression(); }
  Point Get_Point_In_Line(double x) { return p0 + v * x; }
};
int Is_Point_In_Line(Point p, Line l) { return !dcmp((p - l.a) * (l.b - l.a)); }
int Is_Point_In_Segment(Point p, Line l) {
  return !dcmp((p - l.a) * (l.b - l.a)) && dcmp((p - l.a) ^ (p - l.b)) <= 0;
}
double Distance_Point_To_Line(Point p, Line l) {
  Point v1 = l.b - l.a, v2 = p - l.a;
  return fabs(v1 * v2 / v1.Len());
}
double Distance_Point_To_Segment(Point p, Line l) {
  if (l.a == l.b) return (p - l.a).Len();
  Point v1 = p - l.a, v2 = p - l.b, v3 = l.b - l.a;
  if (dcmp(v1 ^ v3) < 0) return v1.Len();
  if (dcmp(v2 ^ v3) > 0) return v2.Len();
  return fabs(v1 * v3 / v3.Len());
}
Point Foot_Point_To_line(Point p, Line l) {
  Point v1 = p - l.a, v2 = p - l.b, v3 = l.b - l.a;
  double len1 = (v1 ^ v3) / v3.Len(), len2 = -1.0 * (v2 ^ v3) / v3.Len();
  return l.a + v3 * (len1 / (len1 + len2));
}
Point Symmetric_Point_About_Line(Point p, Line l) {
  return p + (Foot_Point_To_line(p, l) - p) * 2;
}
Point Line_Line_Cross_Point(Line l1, Line l2) {
  Point v1 = l1.b - l1.a, v2 = l2.b - l2.a, v3 = l1.a - l2.a;
  return l1.a + v1 * ((v2 * v3) / (v1 * v2));
}
int Is_Line_Line_Cross(Line l1, Line l2) {
  return Is_Point_In_Segment(Line_Line_Cross_Point(l1, l2), l2);
}
int Is_Segment_Segment_Cross(Line l1, Line l2) {
  double c1 = (l1.b - l1.a) * (l2.a - l1.a), c2 = (l1.b - l1.a) * (l2.b - l1.a);
  double d1 = (l2.b - l2.a) * (l1.a - l2.a), d2 = (l2.b - l2.a) * (l1.b - l2.a);
  return dcmp(c1) * dcmp(c2) <= 0 && dcmp(d1) * dcmp(d2) <= 0;
};
struct Polygon {
  int n;
  vector<Point> point;
  Polygon(int N = 0) {
    n = N;
    point.clear();
  }
  void clear() {
    n = 0;
    point.clear();
  }
  void Insert(Point p) {
    point.push_back(p);
    ++n;
  }
  Point Gravity_Center() {
    Point re;
    for (int i = 0; i < n; ++i) re.x += point[i].x, re.y += point[i].y;
    return re * (1.0 / n);
  }
  double Area() {
    double re = 0;
    for (int i = 1; i < n - 1; ++i)
      re += (point[i] - point[0]) * (point[i + 1] - point[0]);
    return re / 2.0;
  }
};
int Is_Point_In_Polygon(Point p, Polygon &ply) {
  int cnt = 0;
  double tmp;
  for (int i = 0; i < ply.n; ++i) {
    int j = i < ply.n - 1 ? i + 1 : 0;
    if (Is_Point_In_Segment(p, Line(ply.point[i], ply.point[j]))) return 2;
    if (dcmp(p.y - min(ply.point[i].y, ply.point[j].y)) >= 0 &&
        dcmp(p.y - max(ply.point[i].y, ply.point[j].y)) < 0) {
      tmp = ply.point[i].x + (p.y - ply.point[i].y) /
                                 (ply.point[j].y - ply.point[i].y) *
                                 (ply.point[j].x - ply.point[i].x);
      cnt += (dcmp(tmp - p.x) > 0);
    }
  }
  return cnt & 1;
}
int Is_Point_In_Polygon_(Point p, Polygon &ply) {
  if (dcmp((p - ply.point[0]) * (ply.point[1] - ply.point[0])) > 0 ||
      dcmp((ply.point[ply.n - 1] - ply.point[0]) * (p - ply.point[0])) > 0)
    return 0;
  if (Is_Point_In_Segment(p, Line(ply.point[0], ply.point[1])) ||
      Is_Point_In_Segment(p, Line(ply.point[0], ply.point[ply.n - 1])))
    return 2;
  int l = 1, r = ply.n - 2, mid;
  while (l < r) {
    mid = (l + r + 1) >> 1;
    if (dcmp((ply.point[mid] - ply.point[0]) * (p - ply.point[0])) > 0)
      l = mid;
    else
      r = mid - 1;
  }
  if (dcmp((p - ply.point[l]) * (ply.point[l + 1] - ply.point[l])) > 0)
    return 0;
  if (Is_Point_In_Segment(p, Line(ply.point[l], ply.point[l + 1]))) return 2;
  return 1;
}
Polygon Andrew_Convex_Hull(Polygon &ply) {
  Polygon re;
  sort(ply.point.begin(), ply.point.end());
  int cnt = -1;
  for (int i = 0; i < ply.n; ++i) {
    while (cnt > 0 && dcmp((re.point[cnt] - re.point[cnt - 1]) *
                           (ply.point[i] - re.point[cnt - 1])) < 0)
      cnt--;
    ++cnt;
    if (cnt < re.point.size())
      re.point[cnt] = ply.point[i];
    else
      re.Insert(ply.point[i]);
  }
  int tmp = cnt;
  for (int i = ply.n - 2; i >= 0; --i) {
    while (cnt > tmp && dcmp((re.point[cnt] - re.point[cnt - 1]) *
                             (ply.point[i] - re.point[cnt - 1])) < 0)
      cnt--;
    ++cnt;
    if (cnt < re.point.size())
      re.point[cnt] = ply.point[i];
    else
      re.Insert(ply.point[i]);
  }
  re.n = 0;
  for (vector<Point>::iterator it = re.point.begin(); it != re.point.end();) {
    if (re.n < cnt) {
      ++re.n;
      ++it;
    } else
      it = re.point.erase(it);
  }
  return re;
}
struct Circle {};
};  // namespace Geometric
using namespace Geometric;
const int N = 1e5 + 7, M = 2e4 + 7;
int n, m;
Polygon ply, re;
Point p, pb[M];
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    p.In();
    ply.Insert(p);
  }
  cin >> m;
  for (int i = 1; i <= m; i++) {
    pb[i].In();
    ply.Insert(pb[i]);
  }
  sort(pb + 1, pb + 1 + m);
  re = Andrew_Convex_Hull(ply);
  int flag = 1;
  for (int i = 0; i < re.n; i++) {
    int t = lower_bound(pb + 1, pb + 1 + m, re.point[i]) - pb;
    if (pb[t] == re.point[i]) {
      flag = 0;
      break;
    }
  }
  if (flag)
    cout << "YES";
  else
    cout << "NO";
}

```