#include <bits/stdc++.h>
using namespace std;
int sgn(long long x) { return x < 0 ? -1 : (x > 0 ? 1 : 0); }
struct VEC {
  long long x, y;
  VEC operator+(const VEC& b) const { return VEC{x + b.x, y + b.y}; }
  bool operator==(const VEC& b) const { return x == b.x && y == b.y; }
  bool operator!=(const VEC& b) const { return x != b.x || y != b.y; }
  bool operator<(const VEC& b) const { return y != b.y ? y < b.y : x < b.x; }
  VEC operator-(const VEC& b) const { return VEC{x - b.x, y - b.y}; }
  long long operator*(const VEC& b) const { return x * b.x + y * b.y; }
  long long operator^(const VEC& b) const { return x * b.y - y * b.x; }
  void input() { cin >> x >> y; }
};
template <typename T, typename Comp>
struct SPLAY {
  int c[1000011][2], fa[1000011], tot, root;
  T keys[1000011];
  void Init() { root = tot = 0; }
  bool Side(int rt) { return rt == c[fa[rt]][1]; }
  void Init(int rt, const T& key) {
    c[rt][0] = c[rt][1] = fa[rt] = 0;
    keys[rt] = key;
  }
  void SetSon(int x, int f, int s) {
    if (f) c[f][s] = x;
    if (x) fa[x] = f;
  }
  void RotateUp(int now) {
    int f = fa[now];
    bool side = Side(now);
    SetSon(c[now][!side], f, side);
    SetSon(now, fa[f], Side(f));
    SetSon(f, now, !side);
    if (!fa[now]) root = now;
  }
  void Splay(int now, int to = 0) {
    if (!now) return;
    for (int f = fa[now]; f != to; f = fa[now]) {
      if (fa[f] != to) RotateUp(Side(now) == Side(f) ? f : now);
      RotateUp(now);
    }
  }
  bool Insert(const T& key) {
    bool ret = true;
    if (!root) {
      Init(root = ++tot, key);
    } else {
      int now = root;
      int f;
      while (true) {
        if (!now) {
          Init(now = ++tot, key);
          fa[now] = f;
          c[f][Comp()(keys[f], key)] = now;
          break;
        } else if (keys[now] == key) {
          ret = false;
          break;
        }
        f = now;
        now = c[now][Comp()(keys[now], key)];
      }
      Splay(now);
    }
    return ret;
  }
  int find(const T& key) {
    int now = root;
    while (now && ((Comp()(keys[now], key) || Comp()(key, keys[now]))))
      now = c[now][Comp()(keys[now], key)];
    Splay(now);
    return now;
  }
  int FindPreOrNext_down(int now, bool nex) const {
    if (!c[now][nex]) return 0;
    nex = !nex;
    for (now = c[now][!nex]; c[now][nex]; now = c[now][nex])
      ;
    return now;
  }
  void DelRoot() {
    int now = FindPreOrNext_down(root, false);
    if (!now) {
      root = c[root][1];
      fa[root] = 0;
    } else {
      Splay(now);
      SetSon(c[c[root][1]][1], root, 1);
    }
  }
  void Del(const T& key) {
    int now = find(key);
    if (!now) return;
    if (!c[root][0] || !c[root][1]) {
      root = c[root][0] + c[root][1];
      fa[root] = 0;
    } else {
      DelRoot();
    }
  }
  int PreOrNxt(int now, bool nxt) const {
    if (!c[now][nxt]) {
      int f = fa[now];
      while (f && c[f][!nxt] != now) {
        now = f;
        f = fa[now];
      }
      return f;
    } else {
      now = c[now][nxt];
      while (c[now][!nxt]) {
        now = c[now][!nxt];
      }
      return now;
    }
  }
  void erase(int it) {
    Splay(it);
    DelRoot();
  }
  int lower_bound(const T& key, bool nxt) {
    if (!Insert(key)) {
      return root;
    }
    int now = root;
    if (!c[now][nxt]) {
      Del(key);
      return 0;
    }
    now = FindPreOrNext_down(now, nxt);
    Del(key);
    return now;
  }
  int begin() {
    int now = root;
    while (c[now][0]) now = c[now][0];
    return now;
  }
  constexpr int end() { return 0; }
};
struct down_sgn {
  int operator()(long long x) const { return sgn(x); }
};
struct up_sgn {
  int operator()(long long x) const { return -sgn(x); }
};
template <class XSGN>
struct HalfConvexHull {
  struct CMPX {
    bool operator()(const VEC& a, const VEC& b) const {
      return XSGN()(a.x - b.x) < 0;
    }
  };
  SPLAY<VEC, CMPX> s;
  void Init() { s.Init(); }
  int Pre(int it) { return s.PreOrNxt(it, false); }
  int Nxt(int it) { return s.PreOrNxt(it, true); }
  int it;
  int relation(const VEC& p) {
    it = s.lower_bound(p, true);
    if (it == s.end()) return 0;
    if (it == s.begin()) {
      if (XSGN()(p.x - s.keys[it].x) < 0)
        return 0;
      else
        return XSGN()(p.y - s.keys[it].y) + 1;
    }
    int bef = Pre(it);
    return sgn((s.keys[it] - s.keys[bef]) ^ (p - s.keys[bef])) + 1;
  }
  void Insert(const VEC& p) {
    if (relation(p)) return;
    if (it && s.keys[it].x == p.x) {
      s.erase(it);
    }
    s.Insert(p);
    it = s.root;
    auto pre = Pre(it), nxt = Nxt(it);
    if (pre) {
      for (auto j = Pre(pre); j && ((s.keys[pre] - p) ^ (s.keys[j] - p)) >= 0;
           pre = j, j = Pre(j)) {
        s.erase(pre);
      }
    }
    if (nxt) {
      for (auto j = Nxt(nxt); j && ((s.keys[j] - p) ^ (s.keys[nxt] - p)) >= 0;
           nxt = j, j = Nxt(j)) {
        s.erase(nxt);
      }
    }
  }
};
struct ConvexHull {
  HalfConvexHull<down_sgn> down;
  HalfConvexHull<up_sgn> up;
  void Init() {
    down.Init();
    up.Init();
  }
  int relation(const VEC& p) {
    int r = down.relation(p);
    if (r != 2) return r;
    return up.relation(p);
  }
  void Insert(const VEC& p) {
    down.Insert(p);
    up.Insert(p);
  }
};
int main() {
  static ConvexHull conv;
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  while (n--) {
    VEC p;
    int op;
    cin >> op;
    p.input();
    if (1 == op) {
      conv.Insert(p);
    } else {
      if (conv.relation(p)) {
        cout << "YES\n";
      } else {
        cout << "NO\n";
      }
    }
  }
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

Once a walrus professor Plato asked his programming students to perform the following practical task. 

The students had to implement such a data structure that would support a convex hull on some set of points S. The input to the program had q queries of two types: 

1. Add a point with coordinates (x, y) into the set S. Note that in this case the convex hull of S could have changed, and could have remained the same. 

2. Say whether a point with coordinates (x, y) belongs to an area limited by the convex hull, including the border. 

All the students coped with the task. What about you?

Input

The first line contains an integer q (4 ≤ q ≤ 105). 

Then follow q lines in the following way: "t x y", where t is the query type (1 or 2), and (x, y) are the coordinates of the point ( - 106 ≤ x, y ≤ 106, x and y are integers). 

There is at least one query of type 2.

It is guaranteed that the three queries of the first type follow first and the points given in the queries form a non-degenerative triangle. Also all the points added in S are distinct.

Output

For each query of the second type print one string containing "YES", if the point lies inside the convex hull or on its border. Otherwise, print "NO".

Examples

Input

8
1 0 0
1 2 0
1 2 2
2 1 0
1 0 2
2 1 1
2 2 1
2 20 -1


Output

YES
YES
YES
NO

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int sgn(long long x) { return x < 0 ? -1 : (x > 0 ? 1 : 0); }
struct VEC {
  long long x, y;
  VEC operator+(const VEC& b) const { return VEC{x + b.x, y + b.y}; }
  bool operator==(const VEC& b) const { return x == b.x && y == b.y; }
  bool operator!=(const VEC& b) const { return x != b.x || y != b.y; }
  bool operator<(const VEC& b) const { return y != b.y ? y < b.y : x < b.x; }
  VEC operator-(const VEC& b) const { return VEC{x - b.x, y - b.y}; }
  long long operator*(const VEC& b) const { return x * b.x + y * b.y; }
  long long operator^(const VEC& b) const { return x * b.y - y * b.x; }
  void input() { cin >> x >> y; }
};
template <typename T, typename Comp>
struct SPLAY {
  int c[1000011][2], fa[1000011], tot, root;
  T keys[1000011];
  void Init() { root = tot = 0; }
  bool Side(int rt) { return rt == c[fa[rt]][1]; }
  void Init(int rt, const T& key) {
    c[rt][0] = c[rt][1] = fa[rt] = 0;
    keys[rt] = key;
  }
  void SetSon(int x, int f, int s) {
    if (f) c[f][s] = x;
    if (x) fa[x] = f;
  }
  void RotateUp(int now) {
    int f = fa[now];
    bool side = Side(now);
    SetSon(c[now][!side], f, side);
    SetSon(now, fa[f], Side(f));
    SetSon(f, now, !side);
    if (!fa[now]) root = now;
  }
  void Splay(int now, int to = 0) {
    if (!now) return;
    for (int f = fa[now]; f != to; f = fa[now]) {
      if (fa[f] != to) RotateUp(Side(now) == Side(f) ? f : now);
      RotateUp(now);
    }
  }
  bool Insert(const T& key) {
    bool ret = true;
    if (!root) {
      Init(root = ++tot, key);
    } else {
      int now = root;
      int f;
      while (true) {
        if (!now) {
          Init(now = ++tot, key);
          fa[now] = f;
          c[f][Comp()(keys[f], key)] = now;
          break;
        } else if (keys[now] == key) {
          ret = false;
          break;
        }
        f = now;
        now = c[now][Comp()(keys[now], key)];
      }
      Splay(now);
    }
    return ret;
  }
  int find(const T& key) {
    int now = root;
    while (now && ((Comp()(keys[now], key) || Comp()(key, keys[now]))))
      now = c[now][Comp()(keys[now], key)];
    Splay(now);
    return now;
  }
  int FindPreOrNext_down(int now, bool nex) const {
    if (!c[now][nex]) return 0;
    nex = !nex;
    for (now = c[now][!nex]; c[now][nex]; now = c[now][nex])
      ;
    return now;
  }
  void DelRoot() {
    int now = FindPreOrNext_down(root, false);
    if (!now) {
      root = c[root][1];
      fa[root] = 0;
    } else {
      Splay(now);
      SetSon(c[c[root][1]][1], root, 1);
    }
  }
  void Del(const T& key) {
    int now = find(key);
    if (!now) return;
    if (!c[root][0] || !c[root][1]) {
      root = c[root][0] + c[root][1];
      fa[root] = 0;
    } else {
      DelRoot();
    }
  }
  int PreOrNxt(int now, bool nxt) const {
    if (!c[now][nxt]) {
      int f = fa[now];
      while (f && c[f][!nxt] != now) {
        now = f;
        f = fa[now];
      }
      return f;
    } else {
      now = c[now][nxt];
      while (c[now][!nxt]) {
        now = c[now][!nxt];
      }
      return now;
    }
  }
  void erase(int it) {
    Splay(it);
    DelRoot();
  }
  int lower_bound(const T& key, bool nxt) {
    if (!Insert(key)) {
      return root;
    }
    int now = root;
    if (!c[now][nxt]) {
      Del(key);
      return 0;
    }
    now = FindPreOrNext_down(now, nxt);
    Del(key);
    return now;
  }
  int begin() {
    int now = root;
    while (c[now][0]) now = c[now][0];
    return now;
  }
  constexpr int end() { return 0; }
};
struct down_sgn {
  int operator()(long long x) const { return sgn(x); }
};
struct up_sgn {
  int operator()(long long x) const { return -sgn(x); }
};
template <class XSGN>
struct HalfConvexHull {
  struct CMPX {
    bool operator()(const VEC& a, const VEC& b) const {
      return XSGN()(a.x - b.x) < 0;
    }
  };
  SPLAY<VEC, CMPX> s;
  void Init() { s.Init(); }
  int Pre(int it) { return s.PreOrNxt(it, false); }
  int Nxt(int it) { return s.PreOrNxt(it, true); }
  int it;
  int relation(const VEC& p) {
    it = s.lower_bound(p, true);
    if (it == s.end()) return 0;
    if (it == s.begin()) {
      if (XSGN()(p.x - s.keys[it].x) < 0)
        return 0;
      else
        return XSGN()(p.y - s.keys[it].y) + 1;
    }
    int bef = Pre(it);
    return sgn((s.keys[it] - s.keys[bef]) ^ (p - s.keys[bef])) + 1;
  }
  void Insert(const VEC& p) {
    if (relation(p)) return;
    if (it && s.keys[it].x == p.x) {
      s.erase(it);
    }
    s.Insert(p);
    it = s.root;
    auto pre = Pre(it), nxt = Nxt(it);
    if (pre) {
      for (auto j = Pre(pre); j && ((s.keys[pre] - p) ^ (s.keys[j] - p)) >= 0;
           pre = j, j = Pre(j)) {
        s.erase(pre);
      }
    }
    if (nxt) {
      for (auto j = Nxt(nxt); j && ((s.keys[j] - p) ^ (s.keys[nxt] - p)) >= 0;
           nxt = j, j = Nxt(j)) {
        s.erase(nxt);
      }
    }
  }
};
struct ConvexHull {
  HalfConvexHull<down_sgn> down;
  HalfConvexHull<up_sgn> up;
  void Init() {
    down.Init();
    up.Init();
  }
  int relation(const VEC& p) {
    int r = down.relation(p);
    if (r != 2) return r;
    return up.relation(p);
  }
  void Insert(const VEC& p) {
    down.Insert(p);
    up.Insert(p);
  }
};
int main() {
  static ConvexHull conv;
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  while (n--) {
    VEC p;
    int op;
    cin >> op;
    p.input();
    if (1 == op) {
      conv.Insert(p);
    } else {
      if (conv.relation(p)) {
        cout << "YES\n";
      } else {
        cout << "NO\n";
      }
    }
  }
  return 0;
}

```