#include <bits/stdc++.h>
std::mt19937 rd(1);
struct point_t {
  int x;
  int y;
  point_t(int x_ = 0, int y_ = 0) : x(x_), y(y_) {}
  bool operator<(const point_t& other) const {
    return x < other.x || (x == other.x && y < other.y);
  }
  bool operator>(const point_t& other) const { return other < *this; }
  bool operator<=(const point_t& other) const { return !(*this > other); }
  bool operator>=(const point_t& other) const { return !(*this < other); }
  bool operator==(const point_t& other) const {
    return (*this <= other) && (*this >= other);
  }
  bool operator!=(const point_t& other) const { return !(*this == other); }
  long long operator*(const point_t& other) const {
    return x * (long long)other.x + y * (long long)other.y;
  }
  long long operator^(const point_t& other) const {
    return x * (long long)other.y - y * (long long)other.x;
  }
  point_t operator-(const point_t& other) const {
    return point_t(x - other.x, y - other.y);
  }
  point_t operator+(const point_t& other) const {
    return point_t(x + other.x, y + other.y);
  }
  friend std::ostream& operator<<(std::ostream& out, const point_t& point);
  friend std::istream& operator>>(std::istream& in, point_t& point);
};
std::ostream& operator<<(std::ostream& out, const point_t& point) {
  out << "Point(x:" << point.x << ", y:" << point.y << ")";
  return out;
}
std::istream& operator>>(std::istream& in, point_t& point) {
  in >> point.x >> point.y;
  return in;
}
struct line_t {
  point_t from;
  point_t to;
  line_t() : from(), to() {}
  line_t(const point_t& from_, const point_t& to_) : from(from_), to(to_) {}
  void order() {
    if (from > to) {
      std::swap(from, to);
    }
  }
  long long value_from_point(const point_t& other) const {
    if (to.x == from.x) {
      if (from.y <= other.y && other.y <= to.y) {
        return 0;
      }
      return other.y < from.y ? -1 : 1;
    }
    return (from.y - to.y) * (long long)other.x +
           (to.x - from.x) * (long long)other.y +
           (from.x * (long long)to.y - from.y * (long long)to.x);
  }
  bool operator<(const line_t& other) const {
    return from < other.from || (from == other.from && to.y < other.to.y);
  }
  bool operator>(const line_t& other) const { return other < *this; }
  bool operator<=(const line_t& other) const { return !(*this > other); }
  bool operator>=(const line_t& other) const { return !(*this < other); }
  bool operator==(const line_t& other) const {
    return (*this <= other) && (other <= *this);
  }
  bool operator!=(const line_t& other) const { return !(*this == other); }
  bool operator<(const point_t& other) const {
    return value_from_point(other) < 0;
  }
  bool operator>(const point_t& other) const {
    return value_from_point(other) > 0;
  }
  bool operator<=(const point_t& other) const { return !(*this > other); }
  bool operator>=(const point_t& other) const { return !(*this < other); }
  bool operator==(const point_t& other) const {
    return (*this <= other) && (*this >= other);
  }
  bool operator!=(const point_t& other) const { return !(*this == other); }
  bool contains_point(const point_t& other) const {
    return ((to - from) ^ (other - from)) == 0 &&
           ((to - from) * (other - from)) >= 0 &&
           ((from - to) * (other - to)) >= 0;
  }
  friend std::ostream& operator<<(std::ostream& out, const line_t& line);
  friend std::istream& operator>>(std::istream& in, line_t& line);
};
std::ostream& operator<<(std::ostream& out, const line_t& line) {
  out << "Line<" << line.from << ", " << line.to << ">";
  return out;
}
std::istream& operator>>(std::istream& in, line_t& line) {
  in >> line.from >> line.to;
  return in;
}
struct node_t {
  line_t value;
  int key;
  node_t *left, *right;
  node_t* parent;
  int size;
  node_t(const line_t& value_ = line_t(), int key_ = rd())
      : value(value_),
        key(key_),
        left(nullptr),
        right(nullptr),
        parent(nullptr),
        size(1) {}
};
struct treap_t {
  node_t* root;
  treap_t(node_t* root_ = nullptr) : root(root_) {}
  void merge(const treap_t& right_treap) {
    auto new_treap = recursive_merge_subtrees_(*this, right_treap);
    root = new_treap.root;
  }
  void split(treap_t& left, treap_t& right, point_t split_value) {
    if (!root) {
      left.root = nullptr;
      right.root = nullptr;
      return;
    }
    if (root->value >= split_value) {
      treap_t(root->right).split(left, right, split_value);
      root->right = left.root;
      left = *this;
    } else {
      treap_t(root->left).split(left, right, split_value);
      root->left = right.root;
      right = *this;
    }
    left.update_();
    right.update_();
  }
  node_t* extreme_element(bool leftmost) const {
    node_t* answer = root;
    node_t* current = root;
    while (current) {
      answer = current;
      current = leftmost ? current->left : current->right;
    }
    return answer;
  }
  node_t* insert(line_t line) {
    treap_t left, right;
    split(left, right, line.from);
    auto node = new node_t(line);
    treap_t middle = treap_t(node);
    *this = left;
    merge(middle);
    merge(right);
    return node;
  }
  void erase_by_pointer(node_t* node) {
    auto left = treap_t(node->left);
    auto right = treap_t(node->right);
    node_t* parent = node->parent;
    left.merge(right);
    if (parent) {
      node_t* new_son = nullptr;
      if (left.root) {
        left.root->parent = parent;
        new_son = left.root;
      }
      if (parent->left == node) {
        parent->left = new_son;
      } else {
        parent->right = new_son;
      }
    } else {
      *this = left;
      if (left.root) {
        left.root->parent = nullptr;
      }
    }
    node_t* current = parent;
    while (current) {
      node_t* next_parent = current->parent;
      treap_t(current).update_();
      current = next_parent;
    }
    delete node;
  }
  void print() {
    std::cout << ">>>>TRIE:\n";
    print_(root);
    std::cout << "<<<<\n";
  }

 private:
  treap_t recursive_merge_subtrees_(const treap_t& left, const treap_t& right) {
    if (!left.root || !right.root) {
      return left.root ? left : right;
    }
    if (left.root->key > right.root->key) {
      auto result = recursive_merge_subtrees_(treap_t(left.root->right), right);
      left.root->right = result.root;
      left.update_();
      return left;
    } else {
      auto result = recursive_merge_subtrees_(left, treap_t(right.root->left));
      right.root->left = result.root;
      right.update_();
      return right;
    }
  }
  void update_() const {
    if (root) {
      root->size = 1;
      root->parent = nullptr;
      if (root->left) {
        root->size += root->left->size;
        root->left->parent = root;
      }
      if (root->right) {
        root->size += root->right->size;
        root->right->parent = root;
      }
    }
  }
  void print_(node_t* node, int depth = 0) {
    if (depth > 30) {
      exit(1);
    }
    std::cout << "NODE:" << node << std::endl;
    if (!node) {
      std::cout << "EMPTY" << std::endl;
      return;
    }
    std::cout << node->value << ' ' << node->size << std::endl;
    std::cout << "parent:" << node->parent << ", left:" << node->left
              << ", right:" << node->right << std::endl;
    if (node->left) print_(node->left, depth + 1);
    if (node->right) print_(node->right, depth + 1);
  }
};
int point_position(treap_t treap, point_t point) {
  treap_t left, right;
  treap.split(left, right, point);
  auto nearst_node = left.extreme_element(false);
  if (nearst_node) {
  } else {
  }
  int position;
  if (nearst_node == nullptr) {
    position = 2;
  } else if (nearst_node->value.contains_point(point)) {
    position = 1;
  } else {
    position = (left.root->size % 2 == 0) ? 2 : 0;
  }
  treap = left;
  left.merge(right);
  return position;
}
std::vector<line_t> scan_lines() {
  int n;
  std::cin >> n;
  std::vector<line_t> lines;
  point_t last, first_point;
  std::cin >> last;
  first_point = last;
  for (int i = 0; i < n - 1; i++) {
    point_t current_point;
    std::cin >> current_point;
    if (current_point != last) {
      lines.emplace_back(last, current_point);
    }
    last = current_point;
  }
  if (last != first_point) {
    lines.emplace_back(last, first_point);
  }
  if (lines.empty()) {
    lines.emplace_back(first_point, first_point);
  }
  for (auto& line : lines) {
    line.order();
  }
  return lines;
}
std::vector<point_t> scan_requests() {
  int m;
  std::cin >> m;
  std::vector<point_t> requests(m);
  for (auto& request : requests) {
    std::cin >> request;
  }
  return requests;
}
struct event_t {
  int type;
  line_t line;
  unsigned id;
  bool operator<(const event_t& other) const {
    return line.from < other.line.from ||
           (line.from == other.line.from && type < other.type) ||
           (line.from == other.line.from && type == other.type &&
            line.to.y < other.line.to.y);
  }
};
std::vector<event_t> make_queue(const std::vector<line_t>& lines,
                                const std::vector<point_t>& requests) {
  std::vector<event_t> request_queue(2 * lines.size() + requests.size());
  for (unsigned i = 0; i < lines.size(); i++) {
    request_queue[2 * i] = {0, lines[i], i};
    request_queue[2 * i + 1] = {2, line_t(lines[i].to, lines[i].to), i};
  }
  for (unsigned i = 0; i < requests.size(); i++) {
    request_queue[2 * lines.size() + i] = {1, line_t(requests[i], requests[i]),
                                           i};
  }
  sort(request_queue.begin(), request_queue.end());
  return request_queue;
}
void solve() {
  std::vector<line_t> lines = scan_lines();
  sort(lines.begin(), lines.end());
  std::vector<point_t> requests = scan_requests();
  if (requests.empty()) {
    return;
  }
  auto request_queue = make_queue(lines, requests);
  treap_t treap;
  node_t* node_pointers[lines.size() + requests.size()];
  int answers[requests.size()];
  for (auto& request : request_queue) {
    if (request.type == 0) {
      node_pointers[request.id] = treap.insert(request.line);
    } else if (request.type == 1) {
      answers[request.id] = point_position(treap, request.line.from);
    } else {
      treap.erase_by_pointer(node_pointers[request.id]);
    }
  }
  std::string position_representation[] = {"INSIDE", "BORDER", "OUTSIDE"};
  bool answer = true;
  for (unsigned i = 0; i < requests.size(); i++) {
    if (answers[i]) {
      answer = false;
    }
  }
  std::cout << (answer ? "YES" : "NO");
}
int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  solve();
}

### Prompt

Construct a CPP code solution to the problem outlined:

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>
std::mt19937 rd(1);
struct point_t {
  int x;
  int y;
  point_t(int x_ = 0, int y_ = 0) : x(x_), y(y_) {}
  bool operator<(const point_t& other) const {
    return x < other.x || (x == other.x && y < other.y);
  }
  bool operator>(const point_t& other) const { return other < *this; }
  bool operator<=(const point_t& other) const { return !(*this > other); }
  bool operator>=(const point_t& other) const { return !(*this < other); }
  bool operator==(const point_t& other) const {
    return (*this <= other) && (*this >= other);
  }
  bool operator!=(const point_t& other) const { return !(*this == other); }
  long long operator*(const point_t& other) const {
    return x * (long long)other.x + y * (long long)other.y;
  }
  long long operator^(const point_t& other) const {
    return x * (long long)other.y - y * (long long)other.x;
  }
  point_t operator-(const point_t& other) const {
    return point_t(x - other.x, y - other.y);
  }
  point_t operator+(const point_t& other) const {
    return point_t(x + other.x, y + other.y);
  }
  friend std::ostream& operator<<(std::ostream& out, const point_t& point);
  friend std::istream& operator>>(std::istream& in, point_t& point);
};
std::ostream& operator<<(std::ostream& out, const point_t& point) {
  out << "Point(x:" << point.x << ", y:" << point.y << ")";
  return out;
}
std::istream& operator>>(std::istream& in, point_t& point) {
  in >> point.x >> point.y;
  return in;
}
struct line_t {
  point_t from;
  point_t to;
  line_t() : from(), to() {}
  line_t(const point_t& from_, const point_t& to_) : from(from_), to(to_) {}
  void order() {
    if (from > to) {
      std::swap(from, to);
    }
  }
  long long value_from_point(const point_t& other) const {
    if (to.x == from.x) {
      if (from.y <= other.y && other.y <= to.y) {
        return 0;
      }
      return other.y < from.y ? -1 : 1;
    }
    return (from.y - to.y) * (long long)other.x +
           (to.x - from.x) * (long long)other.y +
           (from.x * (long long)to.y - from.y * (long long)to.x);
  }
  bool operator<(const line_t& other) const {
    return from < other.from || (from == other.from && to.y < other.to.y);
  }
  bool operator>(const line_t& other) const { return other < *this; }
  bool operator<=(const line_t& other) const { return !(*this > other); }
  bool operator>=(const line_t& other) const { return !(*this < other); }
  bool operator==(const line_t& other) const {
    return (*this <= other) && (other <= *this);
  }
  bool operator!=(const line_t& other) const { return !(*this == other); }
  bool operator<(const point_t& other) const {
    return value_from_point(other) < 0;
  }
  bool operator>(const point_t& other) const {
    return value_from_point(other) > 0;
  }
  bool operator<=(const point_t& other) const { return !(*this > other); }
  bool operator>=(const point_t& other) const { return !(*this < other); }
  bool operator==(const point_t& other) const {
    return (*this <= other) && (*this >= other);
  }
  bool operator!=(const point_t& other) const { return !(*this == other); }
  bool contains_point(const point_t& other) const {
    return ((to - from) ^ (other - from)) == 0 &&
           ((to - from) * (other - from)) >= 0 &&
           ((from - to) * (other - to)) >= 0;
  }
  friend std::ostream& operator<<(std::ostream& out, const line_t& line);
  friend std::istream& operator>>(std::istream& in, line_t& line);
};
std::ostream& operator<<(std::ostream& out, const line_t& line) {
  out << "Line<" << line.from << ", " << line.to << ">";
  return out;
}
std::istream& operator>>(std::istream& in, line_t& line) {
  in >> line.from >> line.to;
  return in;
}
struct node_t {
  line_t value;
  int key;
  node_t *left, *right;
  node_t* parent;
  int size;
  node_t(const line_t& value_ = line_t(), int key_ = rd())
      : value(value_),
        key(key_),
        left(nullptr),
        right(nullptr),
        parent(nullptr),
        size(1) {}
};
struct treap_t {
  node_t* root;
  treap_t(node_t* root_ = nullptr) : root(root_) {}
  void merge(const treap_t& right_treap) {
    auto new_treap = recursive_merge_subtrees_(*this, right_treap);
    root = new_treap.root;
  }
  void split(treap_t& left, treap_t& right, point_t split_value) {
    if (!root) {
      left.root = nullptr;
      right.root = nullptr;
      return;
    }
    if (root->value >= split_value) {
      treap_t(root->right).split(left, right, split_value);
      root->right = left.root;
      left = *this;
    } else {
      treap_t(root->left).split(left, right, split_value);
      root->left = right.root;
      right = *this;
    }
    left.update_();
    right.update_();
  }
  node_t* extreme_element(bool leftmost) const {
    node_t* answer = root;
    node_t* current = root;
    while (current) {
      answer = current;
      current = leftmost ? current->left : current->right;
    }
    return answer;
  }
  node_t* insert(line_t line) {
    treap_t left, right;
    split(left, right, line.from);
    auto node = new node_t(line);
    treap_t middle = treap_t(node);
    *this = left;
    merge(middle);
    merge(right);
    return node;
  }
  void erase_by_pointer(node_t* node) {
    auto left = treap_t(node->left);
    auto right = treap_t(node->right);
    node_t* parent = node->parent;
    left.merge(right);
    if (parent) {
      node_t* new_son = nullptr;
      if (left.root) {
        left.root->parent = parent;
        new_son = left.root;
      }
      if (parent->left == node) {
        parent->left = new_son;
      } else {
        parent->right = new_son;
      }
    } else {
      *this = left;
      if (left.root) {
        left.root->parent = nullptr;
      }
    }
    node_t* current = parent;
    while (current) {
      node_t* next_parent = current->parent;
      treap_t(current).update_();
      current = next_parent;
    }
    delete node;
  }
  void print() {
    std::cout << ">>>>TRIE:\n";
    print_(root);
    std::cout << "<<<<\n";
  }

 private:
  treap_t recursive_merge_subtrees_(const treap_t& left, const treap_t& right) {
    if (!left.root || !right.root) {
      return left.root ? left : right;
    }
    if (left.root->key > right.root->key) {
      auto result = recursive_merge_subtrees_(treap_t(left.root->right), right);
      left.root->right = result.root;
      left.update_();
      return left;
    } else {
      auto result = recursive_merge_subtrees_(left, treap_t(right.root->left));
      right.root->left = result.root;
      right.update_();
      return right;
    }
  }
  void update_() const {
    if (root) {
      root->size = 1;
      root->parent = nullptr;
      if (root->left) {
        root->size += root->left->size;
        root->left->parent = root;
      }
      if (root->right) {
        root->size += root->right->size;
        root->right->parent = root;
      }
    }
  }
  void print_(node_t* node, int depth = 0) {
    if (depth > 30) {
      exit(1);
    }
    std::cout << "NODE:" << node << std::endl;
    if (!node) {
      std::cout << "EMPTY" << std::endl;
      return;
    }
    std::cout << node->value << ' ' << node->size << std::endl;
    std::cout << "parent:" << node->parent << ", left:" << node->left
              << ", right:" << node->right << std::endl;
    if (node->left) print_(node->left, depth + 1);
    if (node->right) print_(node->right, depth + 1);
  }
};
int point_position(treap_t treap, point_t point) {
  treap_t left, right;
  treap.split(left, right, point);
  auto nearst_node = left.extreme_element(false);
  if (nearst_node) {
  } else {
  }
  int position;
  if (nearst_node == nullptr) {
    position = 2;
  } else if (nearst_node->value.contains_point(point)) {
    position = 1;
  } else {
    position = (left.root->size % 2 == 0) ? 2 : 0;
  }
  treap = left;
  left.merge(right);
  return position;
}
std::vector<line_t> scan_lines() {
  int n;
  std::cin >> n;
  std::vector<line_t> lines;
  point_t last, first_point;
  std::cin >> last;
  first_point = last;
  for (int i = 0; i < n - 1; i++) {
    point_t current_point;
    std::cin >> current_point;
    if (current_point != last) {
      lines.emplace_back(last, current_point);
    }
    last = current_point;
  }
  if (last != first_point) {
    lines.emplace_back(last, first_point);
  }
  if (lines.empty()) {
    lines.emplace_back(first_point, first_point);
  }
  for (auto& line : lines) {
    line.order();
  }
  return lines;
}
std::vector<point_t> scan_requests() {
  int m;
  std::cin >> m;
  std::vector<point_t> requests(m);
  for (auto& request : requests) {
    std::cin >> request;
  }
  return requests;
}
struct event_t {
  int type;
  line_t line;
  unsigned id;
  bool operator<(const event_t& other) const {
    return line.from < other.line.from ||
           (line.from == other.line.from && type < other.type) ||
           (line.from == other.line.from && type == other.type &&
            line.to.y < other.line.to.y);
  }
};
std::vector<event_t> make_queue(const std::vector<line_t>& lines,
                                const std::vector<point_t>& requests) {
  std::vector<event_t> request_queue(2 * lines.size() + requests.size());
  for (unsigned i = 0; i < lines.size(); i++) {
    request_queue[2 * i] = {0, lines[i], i};
    request_queue[2 * i + 1] = {2, line_t(lines[i].to, lines[i].to), i};
  }
  for (unsigned i = 0; i < requests.size(); i++) {
    request_queue[2 * lines.size() + i] = {1, line_t(requests[i], requests[i]),
                                           i};
  }
  sort(request_queue.begin(), request_queue.end());
  return request_queue;
}
void solve() {
  std::vector<line_t> lines = scan_lines();
  sort(lines.begin(), lines.end());
  std::vector<point_t> requests = scan_requests();
  if (requests.empty()) {
    return;
  }
  auto request_queue = make_queue(lines, requests);
  treap_t treap;
  node_t* node_pointers[lines.size() + requests.size()];
  int answers[requests.size()];
  for (auto& request : request_queue) {
    if (request.type == 0) {
      node_pointers[request.id] = treap.insert(request.line);
    } else if (request.type == 1) {
      answers[request.id] = point_position(treap, request.line.from);
    } else {
      treap.erase_by_pointer(node_pointers[request.id]);
    }
  }
  std::string position_representation[] = {"INSIDE", "BORDER", "OUTSIDE"};
  bool answer = true;
  for (unsigned i = 0; i < requests.size(); i++) {
    if (answers[i]) {
      answer = false;
    }
  }
  std::cout << (answer ? "YES" : "NO");
}
int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  solve();
}

```