#include <bits/stdc++.h>
using namespace std;
inline int sgn(double a) {
  if (a > 1e-9)
    return 1;
  else if (a < -1e-9)
    return -1;
  return 0;
}
struct point {
  double x, y;
  double ang, l;
  point(double x, double y) : x(x), y(y) {
    l = len();
    if (sgn(x) && sgn(y)) ang = angle();
  }
  point() {}
  inline void read() {
    int a, b;
    scanf("%d%d", &a, &b);
    x = a, y = b;
    *this = point(x, y);
  }
  inline double len() const { return sqrt(x * x + y * y); }
  inline double len2() const { return x * x + y * y; }
  inline double angle() { return atan2(y, x); }
  inline double slope() { return y / x; }
  inline int part() { return (int)(y > 0 || (sgn(y) == 0 && x > 0)); }
  inline void normalize() {
    double r = 1.0 / len();
    x *= r;
    y *= r;
  }
  inline point getNormal() {
    point ret = *this;
    ret.normalize();
    return ret;
  }
};
inline point operator-(const point &a, const point &b) {
  return point(a.x - b.x, a.y - b.y);
}
inline point operator+(const point &a, const point &b) {
  return point(a.x + b.x, a.y + b.y);
}
inline point operator*(const point &a, double b) {
  return point(b * a.x, b * a.y);
}
inline point operator*(double b, const point &a) {
  return point(b * a.x, b * a.y);
}
inline double operator*(const point &a, const point &b) {
  return a.x * b.x + a.y * b.y;
}
inline double operator%(const point &a, const point &b) {
  return a.x * b.y - a.y * b.x;
}
inline bool operator==(const point &a, const point &b) {
  return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;
}
inline bool operator!=(const point &a, const point &b) { return !(a == b); }
inline double dist(const point &a, const point &b) { return (a - b).len(); }
bool operator<(point a, point b) {
  double r0 = a.angle(), r1 = b.angle();
  if (sgn(r0 - r1)) return r0 < r1;
  return a.len() + 1e-9 < b.len();
}
int n;
set<point> S;
void print() {
  for (set<point>::iterator i = S.begin(); i != S.end(); i++)
    printf("%lf %lf %lf\n", i->x, i->y, i->ang);
}
set<point>::iterator getPrev(set<point>::iterator p) {
  if (p == S.begin()) p = S.end();
  p--;
  return p;
}
set<point>::iterator getNext(set<point>::iterator p) {
  p++;
  if (p == S.end()) p = S.begin();
  return p;
}
bool Inside(point p) {
  set<point>::iterator t1 = S.upper_bound(p);
  if (t1 == S.end()) t1 = S.begin();
  set<point>::iterator t0 = getPrev(t1);
  return sgn((p - *t0) % (*t1 - *t0)) <= 0;
}
void Insert(point p) {
  if (Inside(p)) return;
  S.insert(p);
  set<point>::iterator tmp = S.lower_bound(p);
  if (tmp != S.begin()) {
    tmp--;
    if (sgn(tmp->ang == p.ang)) S.erase(tmp);
  }
  while (true && S.size() > 3) {
    set<point>::iterator t0 = getPrev(S.lower_bound(p)), t1 = getPrev(t0);
    if (sgn((*t0 - p) % (*t1 - p)) >= 0)
      S.erase(t0);
    else
      break;
  }
  while (true && S.size() > 3) {
    set<point>::iterator t0 = getNext(S.lower_bound(p)), t1 = getNext(t0);
    if (sgn((*t0 - p) % (*t1 - p)) <= 0)
      S.erase(t0);
    else
      break;
  }
}
int main() {
  scanf("%d", &n);
  point S[3];
  for (int i = 0; i < 3; i++) scanf("%*d"), S[i].read();
  point O = (S[0] + S[1] + S[2]) * (1.0 / 3.0);
  ::S.insert(S[0] - O);
  ::S.insert(S[1] - O);
  ::S.insert(S[2] - O);
  n -= 3;
  for (int i = 0; i < n; i++) {
    int ctrl;
    scanf("%d", &ctrl);
    point p;
    p.read();
    p = p - O;
    if (ctrl == 2)
      printf("%s\n", Inside(p) ? "YES" : "NO");
    else
      Insert(p);
  }
  return 0;
}

### Prompt

Your challenge is to write a Cpp solution 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;
inline int sgn(double a) {
  if (a > 1e-9)
    return 1;
  else if (a < -1e-9)
    return -1;
  return 0;
}
struct point {
  double x, y;
  double ang, l;
  point(double x, double y) : x(x), y(y) {
    l = len();
    if (sgn(x) && sgn(y)) ang = angle();
  }
  point() {}
  inline void read() {
    int a, b;
    scanf("%d%d", &a, &b);
    x = a, y = b;
    *this = point(x, y);
  }
  inline double len() const { return sqrt(x * x + y * y); }
  inline double len2() const { return x * x + y * y; }
  inline double angle() { return atan2(y, x); }
  inline double slope() { return y / x; }
  inline int part() { return (int)(y > 0 || (sgn(y) == 0 && x > 0)); }
  inline void normalize() {
    double r = 1.0 / len();
    x *= r;
    y *= r;
  }
  inline point getNormal() {
    point ret = *this;
    ret.normalize();
    return ret;
  }
};
inline point operator-(const point &a, const point &b) {
  return point(a.x - b.x, a.y - b.y);
}
inline point operator+(const point &a, const point &b) {
  return point(a.x + b.x, a.y + b.y);
}
inline point operator*(const point &a, double b) {
  return point(b * a.x, b * a.y);
}
inline point operator*(double b, const point &a) {
  return point(b * a.x, b * a.y);
}
inline double operator*(const point &a, const point &b) {
  return a.x * b.x + a.y * b.y;
}
inline double operator%(const point &a, const point &b) {
  return a.x * b.y - a.y * b.x;
}
inline bool operator==(const point &a, const point &b) {
  return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;
}
inline bool operator!=(const point &a, const point &b) { return !(a == b); }
inline double dist(const point &a, const point &b) { return (a - b).len(); }
bool operator<(point a, point b) {
  double r0 = a.angle(), r1 = b.angle();
  if (sgn(r0 - r1)) return r0 < r1;
  return a.len() + 1e-9 < b.len();
}
int n;
set<point> S;
void print() {
  for (set<point>::iterator i = S.begin(); i != S.end(); i++)
    printf("%lf %lf %lf\n", i->x, i->y, i->ang);
}
set<point>::iterator getPrev(set<point>::iterator p) {
  if (p == S.begin()) p = S.end();
  p--;
  return p;
}
set<point>::iterator getNext(set<point>::iterator p) {
  p++;
  if (p == S.end()) p = S.begin();
  return p;
}
bool Inside(point p) {
  set<point>::iterator t1 = S.upper_bound(p);
  if (t1 == S.end()) t1 = S.begin();
  set<point>::iterator t0 = getPrev(t1);
  return sgn((p - *t0) % (*t1 - *t0)) <= 0;
}
void Insert(point p) {
  if (Inside(p)) return;
  S.insert(p);
  set<point>::iterator tmp = S.lower_bound(p);
  if (tmp != S.begin()) {
    tmp--;
    if (sgn(tmp->ang == p.ang)) S.erase(tmp);
  }
  while (true && S.size() > 3) {
    set<point>::iterator t0 = getPrev(S.lower_bound(p)), t1 = getPrev(t0);
    if (sgn((*t0 - p) % (*t1 - p)) >= 0)
      S.erase(t0);
    else
      break;
  }
  while (true && S.size() > 3) {
    set<point>::iterator t0 = getNext(S.lower_bound(p)), t1 = getNext(t0);
    if (sgn((*t0 - p) % (*t1 - p)) <= 0)
      S.erase(t0);
    else
      break;
  }
}
int main() {
  scanf("%d", &n);
  point S[3];
  for (int i = 0; i < 3; i++) scanf("%*d"), S[i].read();
  point O = (S[0] + S[1] + S[2]) * (1.0 / 3.0);
  ::S.insert(S[0] - O);
  ::S.insert(S[1] - O);
  ::S.insert(S[2] - O);
  n -= 3;
  for (int i = 0; i < n; i++) {
    int ctrl;
    scanf("%d", &ctrl);
    point p;
    p.read();
    p = p - O;
    if (ctrl == 2)
      printf("%s\n", Inside(p) ? "YES" : "NO");
    else
      Insert(p);
  }
  return 0;
}

```