#include <bits/stdc++.h>
using namespace std;
template <class T>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
template <class T>
T readValue(string s) {
  T result;
  istringstream sin(s);
  sin >> result;
  return result;
}
string readString() {
  string ret_val;
  getline(std::cin, ret_val);
  return ret_val;
}
template <class T>
void initArray(T *arr, int size, T value) {
  for (int i = 0; i < size; i++) arr[i] = value;
}
template <class T>
inline T gcd(T a, T b) {
  return (!a) ? b : gcd(b % a, a);
}
template <class T>
inline T mod(T a, T p) {
  a %= p;
  return (a < 0) ? a + p : a;
}
template <class T>
inline int num_bits(T n) {
  return (!n) ? 0 : 1 + numbits(n & (n - 1));
}
template <class T>
inline T inverse(T a, T m) {
  a = mod<T>(a, m);
  return (a == 1) ? 1 : mod((1 - m * inverse(m % a, a)) / a, m);
}
template <class T>
inline bool is_prime(T a) {
  T lim = (T)sqrt((double)a);
  for (T i = 2; i <= T(lim + 1E-9); i++)
    if (a % i == 0) return false;
  return true;
}
template <class T>
inline T power(T a, T p, T mod) {
  if (!p) return 1;
  T temp = power(a, p >> 1, mod);
  temp = (temp * temp) % mod;
  if (p & 1) temp = (temp * a) % mod;
  return temp;
}
void get_primes(int start, int end, vector<int> &vi) {
  int *p = new int[end + 1];
  initArray<int>(p, end + 1, 0);
  p[1] = 1;
  for (int i = 2; i <= end; i++) {
    if (!p[i]) {
      if (i >= start) vi.push_back(i);
      for (int j = 2 * i; j <= end; j += i) p[j] = 1;
    }
  }
  delete[] p;
}
bool dfs(int current, int final, int total, int *visited, int **edges,
         bool flow) {
  if (current == final) return true;
  if (visited[current]) return false;
  visited[current] = true;
  for (int i = 0; i < total; i++)
    if (edges[current][i] && dfs(i, final, total, visited, edges, flow)) {
      if (flow) {
        edges[current][i]--;
        edges[i][current]++;
      }
      return true;
    }
  return false;
}
int flow(int in, int out, int total, int **edges) {
  int result = 0;
  int *visited = new int[total];
  while (initArray<int>(visited, total, 0),
         dfs(in, out, total, visited, edges, true))
    result++;
  delete[] visited;
  return result;
}
void create_set(int x, int *P, int *rank) {
  P[x] = x;
  rank[x] = 0;
}
int find_set(int x, int *P) {
  if (x != P[x]) P[x] = find_set(P[x], P);
  return P[x];
}
bool merge_sets(int x, int y, int *P, int *rank) {
  int Px = find_set(x, P);
  int Py = find_set(y, P);
  if (Px == Py) return false;
  if (rank[Px] > rank[Py])
    P[Py] = Px;
  else
    P[Px] = Py;
  if (rank[Px] == rank[Py]) rank[Py]++;
  return true;
}
template <typename T>
int read_cum_freq(int index, T *tree) {
  int sum = 0;
  while (index) {
    sum += tree[index];
    index -= (index & -index);
  }
  return sum;
}
template <typename T>
void upd_freq(int index, int mxIndex, int value, T *tree) {
  while (index <= mxIndex) {
    tree[index] += value;
    index += (index & -index);
  }
}
template <typename T>
int read_freq(int index, T *tree) {
  return read_cum_freq(index, tree) - read_cum_freq(index - 1, tree);
}
void build_failure_function(const string &str, int *temp_arr) {
  temp_arr[0] = temp_arr[1] = 0;
  for (int i = 2; i <= ((int)(str).size()); i++) {
    temp_arr[i] = -1;
    for (int ind = temp_arr[i - 1]; temp_arr[i] == -1; ind = temp_arr[ind]) {
      if (str[ind] == str[i - 1]) {
        temp_arr[i] = ind + 1;
      } else if (ind == 0) {
        temp_arr[i] = 0;
      }
    }
  }
}
void KMP(const string &text, const string &pattern, int *res) {
  int *temp_arr = new int[((int)(pattern).size()) + 1];
  build_failure_function(pattern, temp_arr);
  int i = 0;
  int ind = 0;
  while (i < ((int)(text).size())) {
    if (text[i] == pattern[ind]) {
      res[i] = ++ind;
      if (res[i] == ((int)(pattern).size())) {
        ind = temp_arr[ind];
      }
      i++;
    } else if (ind == 0) {
      res[i++] = 0;
    } else {
      ind = temp_arr[ind];
    }
  }
  delete[] temp_arr;
}
void setup(int value, string name) {
  string name_in = name + ".in";
  string name_out = name + ".out";
  freopen(name_in.c_str(), "r", stdin);
  if (value) {
    freopen(name_out.c_str(), "w", stdout);
  }
}
long long px, py;
int get_quart(long long dx, long long dy) {
  if (dx >= 0) return (dy >= 0) ? 0 : 3;
  return (dy >= 0) ? 1 : 2;
}
struct cmpor {
  bool operator()(const pair<long long, long long> &p1,
                  const pair<long long, long long> &p2) const {
    long long dx1 = p1.first - px;
    long long dy1 = p1.second - py;
    long long dx2 = p2.first - px;
    long long dy2 = p2.second - py;
    int q1 = get_quart(dx1, dy1);
    int q2 = get_quart(dx2, dy2);
    if (q1 != q2) return q1 < q2;
    return dx1 * dy2 - dx2 * dy1 > 0;
  }
};
set<pair<long long, long long>, cmpor>::iterator prev(
    set<pair<long long, long long>, cmpor>::iterator it,
    set<pair<long long, long long>, cmpor> &st) {
  if (it == st.begin()) {
    it = st.end();
  }
  it--;
  return it;
}
set<pair<long long, long long>, cmpor>::iterator next(
    set<pair<long long, long long>, cmpor>::iterator it,
    set<pair<long long, long long>, cmpor> &st) {
  it++;
  if (it == st.end()) it = st.begin();
  return it;
}
int main() {
  int n;
  std::cin >> n;
  n -= 3;
  vector<int> tx, ty;
  for (int i = 0; i < 3; i++) {
    int t, x, y;
    std::cin >> t >> x >> y;
    tx.push_back(x << 2);
    ty.push_back(y << 2);
  }
  px = (((tx[0] + tx[1]) >> 1) + tx[2]) >> 1;
  py = (((ty[0] + ty[1]) >> 1) + ty[2]) >> 1;
  set<pair<long long, long long>, cmpor> ds;
  for (int i = 0; i < 3; i++) {
    pair<long long, long long> pr(tx[i], ty[i]);
    ds.insert(pr);
  }
  for (int i = 0; i < n; i++) {
    int t, x, y;
    std::cin >> t >> x >> y;
    x <<= 2;
    y <<= 2;
    pair<long long, long long> pr(x, y);
    set<pair<long long, long long>, cmpor>::iterator it = ds.lower_bound(pr),
                                                     it1, it2, it3;
    if (it == ds.end()) {
      it--;
      it1 = it;
      it2 = ds.begin();
    } else if (it == ds.begin()) {
      it2 = it;
      it1 = ds.end();
      it1--;
    } else {
      it2 = it;
      it--;
      it1 = it;
    }
    long long dx = it2->first - it1->first;
    long long dy = it2->second - it1->second;
    long long dx2 = x - it1->first;
    long long dy2 = y - it1->second;
    long long orient = dx * dy2 - dy * dx2;
    bool inside = (orient >= 0);
    if (t == 1) {
      if (inside) {
        continue;
      }
      while (true) {
        it3 = next(it2, ds);
        long long dx = it3->first - it2->first;
        long long dy = it3->second - it2->second;
        long long dx2 = x - it2->first;
        long long dy2 = y - it2->second;
        long long orient = dx * dy2 - dy * dx2;
        if (orient > 0) break;
        ds.erase(it2);
        it2 = it3;
      }
      while (true) {
        it3 = prev(it1, ds);
        long long dx = it3->first - it1->first;
        long long dy = it3->second - it1->second;
        long long dx2 = x - it1->first;
        long long dy2 = y - it1->second;
        long long orient = dx * dy2 - dy * dx2;
        if (orient < 0) break;
        ds.erase(it1);
        it1 = it3;
      }
      ds.insert(pr);
    } else {
      if (inside)
        std::cout << "YES" << std::endl;
      else
        std::cout << "NO" << std::endl;
    }
  }
  return 0;
}

### Prompt

Please create a solution in cpp to the following problem:

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;
template <class T>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
template <class T>
T readValue(string s) {
  T result;
  istringstream sin(s);
  sin >> result;
  return result;
}
string readString() {
  string ret_val;
  getline(std::cin, ret_val);
  return ret_val;
}
template <class T>
void initArray(T *arr, int size, T value) {
  for (int i = 0; i < size; i++) arr[i] = value;
}
template <class T>
inline T gcd(T a, T b) {
  return (!a) ? b : gcd(b % a, a);
}
template <class T>
inline T mod(T a, T p) {
  a %= p;
  return (a < 0) ? a + p : a;
}
template <class T>
inline int num_bits(T n) {
  return (!n) ? 0 : 1 + numbits(n & (n - 1));
}
template <class T>
inline T inverse(T a, T m) {
  a = mod<T>(a, m);
  return (a == 1) ? 1 : mod((1 - m * inverse(m % a, a)) / a, m);
}
template <class T>
inline bool is_prime(T a) {
  T lim = (T)sqrt((double)a);
  for (T i = 2; i <= T(lim + 1E-9); i++)
    if (a % i == 0) return false;
  return true;
}
template <class T>
inline T power(T a, T p, T mod) {
  if (!p) return 1;
  T temp = power(a, p >> 1, mod);
  temp = (temp * temp) % mod;
  if (p & 1) temp = (temp * a) % mod;
  return temp;
}
void get_primes(int start, int end, vector<int> &vi) {
  int *p = new int[end + 1];
  initArray<int>(p, end + 1, 0);
  p[1] = 1;
  for (int i = 2; i <= end; i++) {
    if (!p[i]) {
      if (i >= start) vi.push_back(i);
      for (int j = 2 * i; j <= end; j += i) p[j] = 1;
    }
  }
  delete[] p;
}
bool dfs(int current, int final, int total, int *visited, int **edges,
         bool flow) {
  if (current == final) return true;
  if (visited[current]) return false;
  visited[current] = true;
  for (int i = 0; i < total; i++)
    if (edges[current][i] && dfs(i, final, total, visited, edges, flow)) {
      if (flow) {
        edges[current][i]--;
        edges[i][current]++;
      }
      return true;
    }
  return false;
}
int flow(int in, int out, int total, int **edges) {
  int result = 0;
  int *visited = new int[total];
  while (initArray<int>(visited, total, 0),
         dfs(in, out, total, visited, edges, true))
    result++;
  delete[] visited;
  return result;
}
void create_set(int x, int *P, int *rank) {
  P[x] = x;
  rank[x] = 0;
}
int find_set(int x, int *P) {
  if (x != P[x]) P[x] = find_set(P[x], P);
  return P[x];
}
bool merge_sets(int x, int y, int *P, int *rank) {
  int Px = find_set(x, P);
  int Py = find_set(y, P);
  if (Px == Py) return false;
  if (rank[Px] > rank[Py])
    P[Py] = Px;
  else
    P[Px] = Py;
  if (rank[Px] == rank[Py]) rank[Py]++;
  return true;
}
template <typename T>
int read_cum_freq(int index, T *tree) {
  int sum = 0;
  while (index) {
    sum += tree[index];
    index -= (index & -index);
  }
  return sum;
}
template <typename T>
void upd_freq(int index, int mxIndex, int value, T *tree) {
  while (index <= mxIndex) {
    tree[index] += value;
    index += (index & -index);
  }
}
template <typename T>
int read_freq(int index, T *tree) {
  return read_cum_freq(index, tree) - read_cum_freq(index - 1, tree);
}
void build_failure_function(const string &str, int *temp_arr) {
  temp_arr[0] = temp_arr[1] = 0;
  for (int i = 2; i <= ((int)(str).size()); i++) {
    temp_arr[i] = -1;
    for (int ind = temp_arr[i - 1]; temp_arr[i] == -1; ind = temp_arr[ind]) {
      if (str[ind] == str[i - 1]) {
        temp_arr[i] = ind + 1;
      } else if (ind == 0) {
        temp_arr[i] = 0;
      }
    }
  }
}
void KMP(const string &text, const string &pattern, int *res) {
  int *temp_arr = new int[((int)(pattern).size()) + 1];
  build_failure_function(pattern, temp_arr);
  int i = 0;
  int ind = 0;
  while (i < ((int)(text).size())) {
    if (text[i] == pattern[ind]) {
      res[i] = ++ind;
      if (res[i] == ((int)(pattern).size())) {
        ind = temp_arr[ind];
      }
      i++;
    } else if (ind == 0) {
      res[i++] = 0;
    } else {
      ind = temp_arr[ind];
    }
  }
  delete[] temp_arr;
}
void setup(int value, string name) {
  string name_in = name + ".in";
  string name_out = name + ".out";
  freopen(name_in.c_str(), "r", stdin);
  if (value) {
    freopen(name_out.c_str(), "w", stdout);
  }
}
long long px, py;
int get_quart(long long dx, long long dy) {
  if (dx >= 0) return (dy >= 0) ? 0 : 3;
  return (dy >= 0) ? 1 : 2;
}
struct cmpor {
  bool operator()(const pair<long long, long long> &p1,
                  const pair<long long, long long> &p2) const {
    long long dx1 = p1.first - px;
    long long dy1 = p1.second - py;
    long long dx2 = p2.first - px;
    long long dy2 = p2.second - py;
    int q1 = get_quart(dx1, dy1);
    int q2 = get_quart(dx2, dy2);
    if (q1 != q2) return q1 < q2;
    return dx1 * dy2 - dx2 * dy1 > 0;
  }
};
set<pair<long long, long long>, cmpor>::iterator prev(
    set<pair<long long, long long>, cmpor>::iterator it,
    set<pair<long long, long long>, cmpor> &st) {
  if (it == st.begin()) {
    it = st.end();
  }
  it--;
  return it;
}
set<pair<long long, long long>, cmpor>::iterator next(
    set<pair<long long, long long>, cmpor>::iterator it,
    set<pair<long long, long long>, cmpor> &st) {
  it++;
  if (it == st.end()) it = st.begin();
  return it;
}
int main() {
  int n;
  std::cin >> n;
  n -= 3;
  vector<int> tx, ty;
  for (int i = 0; i < 3; i++) {
    int t, x, y;
    std::cin >> t >> x >> y;
    tx.push_back(x << 2);
    ty.push_back(y << 2);
  }
  px = (((tx[0] + tx[1]) >> 1) + tx[2]) >> 1;
  py = (((ty[0] + ty[1]) >> 1) + ty[2]) >> 1;
  set<pair<long long, long long>, cmpor> ds;
  for (int i = 0; i < 3; i++) {
    pair<long long, long long> pr(tx[i], ty[i]);
    ds.insert(pr);
  }
  for (int i = 0; i < n; i++) {
    int t, x, y;
    std::cin >> t >> x >> y;
    x <<= 2;
    y <<= 2;
    pair<long long, long long> pr(x, y);
    set<pair<long long, long long>, cmpor>::iterator it = ds.lower_bound(pr),
                                                     it1, it2, it3;
    if (it == ds.end()) {
      it--;
      it1 = it;
      it2 = ds.begin();
    } else if (it == ds.begin()) {
      it2 = it;
      it1 = ds.end();
      it1--;
    } else {
      it2 = it;
      it--;
      it1 = it;
    }
    long long dx = it2->first - it1->first;
    long long dy = it2->second - it1->second;
    long long dx2 = x - it1->first;
    long long dy2 = y - it1->second;
    long long orient = dx * dy2 - dy * dx2;
    bool inside = (orient >= 0);
    if (t == 1) {
      if (inside) {
        continue;
      }
      while (true) {
        it3 = next(it2, ds);
        long long dx = it3->first - it2->first;
        long long dy = it3->second - it2->second;
        long long dx2 = x - it2->first;
        long long dy2 = y - it2->second;
        long long orient = dx * dy2 - dy * dx2;
        if (orient > 0) break;
        ds.erase(it2);
        it2 = it3;
      }
      while (true) {
        it3 = prev(it1, ds);
        long long dx = it3->first - it1->first;
        long long dy = it3->second - it1->second;
        long long dx2 = x - it1->first;
        long long dy2 = y - it1->second;
        long long orient = dx * dy2 - dy * dx2;
        if (orient < 0) break;
        ds.erase(it1);
        it1 = it3;
      }
      ds.insert(pr);
    } else {
      if (inside)
        std::cout << "YES" << std::endl;
      else
        std::cout << "NO" << std::endl;
    }
  }
  return 0;
}

```