(Analysis by Richard Peng)

This problem is a dynamic (insertion of points) version of "a highway and seven dwarfs" from CEOI 2002. It asks to support a point set (the set of cows) under insertion, and queries of whether a line (the fence) separates the point set.

One way to solve it is by a systematic reduction of decomposable problems under insertion to $O(log n)$ static versions. A problem is decomposable if for any partition of the input data (points here), solutions on the two halves can be pieced together to form an overall solution.

Whether a point set is separated by a line is not decomposable under splitting of point sets: we can always split the point set into those above the line, and those below. However, the question of whether there is a point above the line is decomposable: there is a point above the line if and only if there is one in either half of the data that we split into.

This subproblem has a solution that runs in $O(n log n)$ time preprocessing and $O(log n)$ time per query via convex hulls. It is described in details in the solution to the CEOI 02 problem mentioned above.

A simple way to use this data structure in an incremental setting is to store the last say, 500, new points in a buffer, and rebuild the entire data structure when the buffer is full. The overall structure is rebuilt 100,000 / 500 = 200 times, while each query takes $O(log n)$ for the points in the hull, and scanning through the buffer linearly. This suffices for full points, and theoretically optimizing the buffer size at $n^{0.5}$ gives a total performance of about $O(n^{1.5})$.

To obtain an even faster solution, instead of having a buffer, we use another copy of this data structure. When unrolled, this corresponds to having copies of data structures storing exponentially larger point sets. Whenever a smaller set fills up, it can be merged with the set that's one larger than it. A systematic treatment of this setup can be found in pages 1-14 of this report, with more details in the rest of Section 3.

Below is Mark Gordon's code that implements this sequence of copies idea.

#include <iostream>
#include <algorithm>
#include <vector>
#include <complex>
#include <cmath>
#include <cstdio>

using namespace std;

// #define USE_FLOAT

// #define USE_RELATIVE_ERROR

#ifdef USE_FLOAT
#define EPS 1e-9
typedef double num;
#else
#define EPS 0
typedef long long num;
#endif

inline num nabs(num x) {
  return x < 0 ? -x : x;
}

bool num_lt(num X, num Y) {
#ifdef USE_RELATIVE_ERROR
  return X + max(num(1), nabs(Y)) * EPS < Y;
#else
  return X + EPS < Y;
#endif
}

bool num_lteq(num X, num Y) {
#ifdef USE_RELATIVE_ERROR
  return X <= Y + max(num(1), nabs(Y)) * EPS;
#else
  return X <= Y + EPS;
#endif
}

bool num_eq(num X, num Y) {
#ifdef USE_FLOAT
  return num_lteq(X, Y) && num_lteq(Y, X);
#else
  return X == Y;
#endif
}

typedef complex<num> point;
typedef vector<point> poly;

num cp(point A, point B, point C = point(0, 0)) {
  return imag(conj(A - C) * (B - C));
}

/* Returns true if C is strictly counter-clockwise AB in cartesian coordinates.
 * In other words as you walk from A to B, C would be on your left.  */
bool ccw(point A, point B, point C) {
  return num_lt(0, cp(A, B, C));
}

bool ccweq(point A, point B, point C) {
  return num_lteq(0, cp(A, B, C));
}

num dot(point A, point B, point C = point(0, 0)) {
  return real(conj(A - C) * (B - C));
}

point pivot;
bool pointCmp(point A, point B) {
  return make_pair(A.real(), A.imag()) < make_pair(B.real(), B.imag());
}
bool angleCmp(point A, point B) {
  num c = cp(pivot, A, B);
  return num_eq(c, 0) && dot(A, A, pivot) < dot(B, B, pivot) || num_lt(0, c);
}
void unwind(poly& P, point A) {
  int sz = P.size();
  while(sz > 1 && ccweq(A, P[sz - 1], P[sz - 2])) --sz;
  P.resize(sz);
}

/* Computes the convex hull of the list of points P.  Returns the points
 * defining the convex hull in ccw order. */
poly hull(poly P) {
  swap(P[0], *min_element(P.begin(), P.end(), pointCmp));
  pivot = P[0];
  sort(P.begin() + 1, P.end(), angleCmp);

  poly ret(1, pivot);
  for(int i = 1; i < P.size(); i++) {
    unwind(ret, P[i]);
    ret.push_back(P[i]);
  }
  if(ret.size() > 2) {
    unwind(ret, pivot);
  }
  return ret;
}

/* Returns true if x comes before y when doing a radially sweep around the
 * origin starting from the direction pointed by base.
 */
bool radial_compare(point x, point y, point base = point(1, 0)) {
  num cx = cp(base, x);
  num cy = cp(base, y);
  if (num_eq(cx, 0)) {
    cx = dot(base, x);
  }
  if (num_eq(cy, 0)) {
    cy = dot(base, y);
  }
  if ((cx < 0) == (cy < 0)) {
    return ccw(0, x, y);
  }
  return cy < 0;
}

/* Given a convex poly in ccw order find the max dot product of any point within
 * it with pt. */
num convex_max_dot(const poly& P, point pt) {
  int lo = 0;
  int hi = P.size() - 1;
  point base = P[0] - P.back();
  while (lo < hi) {
    int md = (lo + hi + 1) / 2;
    point v = P[md] - P[md ? md - 1 : P.size() - 1];

    if (radial_compare(v, pt * point(0, 1), base)) {
      lo = md;
    } else {
      hi = md - 1;
    }
  }
  return dot(P[lo], pt);
}

struct dyn_hull {
  dyn_hull() {
  }

  void add(point pt) {
    poly p(1, pt);
    for (int i = 0; i < hulls.size(); i++) {
      if (hulls[i].empty()) {
        hulls[i] = hull(p);
        return;
      }
      for (int j = 0; j < hulls[i].size(); j++) {
        p.push_back(hulls[i][j]);
      }
      hulls[i].clear();
    }
    hulls.push_back(hull(p));
  }

  num max_dot(point pt) {
    num ret = 0;
    bool init = false;
    for (int i = 0; i < hulls.size(); i++) {
      if (hulls[i].empty()) {
        continue;
      }
      num res = convex_max_dot(hulls[i], pt);
      if (!init || res > ret) {
        init = true;
        ret = res;
      }
    }
    return ret;
  }

  bool empty() {
    return hulls.empty();
  }

  vector<poly> hulls;
};

int main() {
  ios_base::sync_with_stdio(false);
  freopen("fencing.in", "r", stdin);
  freopen("fencing.out", "w", stdout);

  int N, Q;
  cin >> N >> Q;

  poly h0;
  for (int i = 0; i < N; i++) {
    num x, y;
    cin >> x >> y;
    h0.push_back(point(x, y));
  }
  h0 = hull(h0);

  dyn_hull h;
  for (int i = 0; i < Q; i++) {
    int cmd;
    cin >> cmd;
    if (cmd == 1) {
      num x, y;
      cin >> x >> y;
      h.add(point(x, y));
    } else {
      num a, b, c;
      cin >> a >> b >> c;
      point pt(a, b);
      
      if ((
            dot(h0[0], pt) <= c ||
            -convex_max_dot(h0, -pt) <= c ||
            (!h.empty() && -h.max_dot(-pt) <= c)
          ) && (
            dot(h0[0], pt) >= c ||
            convex_max_dot(h0, pt) >= c ||
            (!h.empty() && h.max_dot(pt) >= c)
          )
        ) {
        cout << "NO\n";
      } else {
        cout << "YES\n";
      }
    }
  }

  return 0;
}