#include #include #include #include #include #include #define EPS 1e-12 #define rep(E, F) for (E = 0; E < (F); E++) #define per(E, F) for (E = (F) - 1; E >= 0; E--) int min(int a, int b) { if (a > b) return b; return a; } int max(int a, int b) { if (a < b) return b; return a; } typedef double complex pt; typedef long long ll; typedef struct { int t, q, x, y, r; } query; int get_int(); typedef struct { pt* a; int n, s; } list; list* list_init(); void list_free(list*); pt list_access(list*, int); void list_remove(list*, int); void list_insert(list*, int, pt); int ccw(pt a, pt b, pt c) { if (cabs(a - b) < EPS || fabs(cimag((c - a)/(b - a))) < EPS) return 0; return cimag((c - a)/(b - a)) > 0.0 ? 1 : -1; } pt piv; int cmp(const void* p1, const void* p2) { pt a = *(pt*)p1, b = *(pt*)p2; if (fabs(carg(a - piv) - carg(b - piv)) > EPS) return carg(a - piv) < carg(b - piv) ? -1 : 1; if (fabs(cabs(a - piv) - cabs(b - piv)) < EPS) return 0; return cabs(a - piv) < cabs(b - piv) ? -1 : 1; } int convex_hull(pt* p, pt* h, int n) { if (n == 0) return 0; int j = 0, i, mn = 0; for (i = 1; i < n; i++) if (cimag(p[i]) < cimag(p[mn]) || cimag(p[i]) == cimag(p[mn]) && creal(p[i]) < creal(p[mn])) mn = i; pt t = p[mn]; p[mn] = p[0]; p[0] = t; piv = p[0]; qsort(p + 1, n - 1, sizeof(p[1]), cmp); for (i = 1; i < n && cabs(p[0] - p[i]) < EPS; i++); if (i == n) h[j++] = p[0]; else if (i == n - 1) h[j++] = p[0], h[j++] = p[n - 1]; if (i >= n - 1) return j; h[j++] = p[n - 1], h[j++] = p[0], h[j++] = p[i]; if (ccw(h[0], h[1], h[2]) == 0) return j - (cabs(h[0] - h[1]) < EPS ? 2 : 1); for (i++; i < n;) (cabs(h[j - 1] - p[i]) > EPS && ccw(h[j - 2], h[j - 1], p[i]) == 1) ? (h[j++] = p[i++]) : j--; return --j; } int on_segment(pt a, pt b, pt p) { // is |p| on the segment ||? if (fabs(creal(a) - creal(b)) < EPS) return on_segment(a*I, b*I, p*I); if (ccw(a, b, p) != 0) return 0; if (creal(p) + EPS < fmin(creal(a), creal(b))) return 0; if (creal(p) - EPS > fmax(creal(a), creal(b))) return 0; return 1; } int search(list* l, double a) { int r = 1, s = l->n; // the first element is always (0, 0). while (r < s) { int m = (r + s)/2; double h = carg(list_access(l, m)); if (a < h) s = m; else r = m + 1; } return r; } int is_in_hull(list* l, pt p) { int r = search(l, carg(p)); if (l->n < 3) return 0; if (creal(p) < EPS) return cimag(p) - EPS < cimag(list_access(l, l->n - 1)); if (cimag(p) < EPS) return creal(p) - EPS < creal(list_access(l, 1)); return ccw(list_access(l, (r - 1 + l->n)%l->n), list_access(l, r%l->n), p) != -1; } void add_to_hull(list* l, pt p) { if (is_in_hull(l, p)) return; int r = search(l, carg(p)); if (l->n < 3) { // this will always make a box. list_insert(l, r, p); return; } pt p1 = list_access(l, (r - 1 + l->n)%l->n), p2 = list_access(l, r%l->n); list_insert(l, r, p); while (ccw(list_access(l, (r - 2 + l->n)%l->n), list_access(l, (r - 1 + l->n)%l->n), list_access(l, r%l->n)) != 1) { list_remove(l, (r - 1 + l->n)%l->n); if (r != 0) r--; } while (ccw(list_access(l, r%l->n), list_access(l, (r + 1)%l->n), list_access(l, (r + 2)%l->n)) != 1) { list_remove(l, (r + 1)%l->n); if (r == l->n - 1) r--; // TODO: Make case that fails when this line is missing. } } #define MAXN 200000 pt a[3*MAXN + 1], g[3*MAXN + 1], h[3*MAXN + 1]; int main() { int i, j, n = get_int(), m, q, gg = 0; int f[n]; rep(i, n) { double x = get_int(), y = get_int(); a[3*i + 0] = x + y*I; a[3*i + 1] = x; a[3*i + 2] = y*I; } q = get_int(); query b[q]; per(i, q) { b[i].q = getchar(); getchar(); if (b[i].q == 'c') b[i].t = get_int(), b[i].x = get_int(), b[i].y = get_int(); else b[i].x = get_int() - 1, b[i].y = -1; } rep(i, n) f[i] = 0; rep(i, q) if (b[i].q == 'q') f[b[i].x] = 1; rep(i, n) if (!f[i]) g[gg++] = a[3*i], g[gg++] = a[3*i + 1], g[gg++] = a[3*i + 2]; g[gg++] = 0; m = convex_hull(g, h, gg); list* l = list_init(); j = 0; rep(i, m) if (carg(h[i]) < carg(h[j])) j = i; rep(i, m) list_insert(l, l->n, h[(j + i)%m]); rep(i, q) { if (b[i].q == 'c') b[i].r = is_in_hull(l, 1.0*b[i].x/b[i].t + 1.0*b[i].y*I/b[i].t); else { add_to_hull(l, a[3*b[i].x]); add_to_hull(l, a[3*b[i].x + 1]); add_to_hull(l, a[3*b[i].x + 2]); } } per(i, q) if (b[i].q == 'c') printf("%s\n", b[i].r ? "no" : "yes"); list_free(l); return 0; } int get_int() { int ret = 0; char c = getchar(); int sgn; while (1) { if (c == EOF) return EOF; if (c >= '0' && c <= '9') { sgn = 1; break; } if (c == '-') { c = getchar(); if (c < '0' || c > '9') continue; sgn = -1; break; } c = getchar(); } while (1) { ret = ret*10 + c - '0'; c = getchar(); if (c < '0' || c > '9') return sgn*ret; } } /* LIST */ list* list_init() { list* r = malloc(sizeof(*r)); r->n = 0; r->s = 128; r->a = malloc(sizeof(pt)*r->s); return r; } void list_free(list *l) { free(l->a); free(l); } pt list_access(list *l, int x) { assert(x < l->s); assert(x < l->n); return l->a[x]; } void list_remove(list *l, int x) { int i; for (i = x; i < l->n - 1; i++) l->a[i] = l->a[i + 1]; l->n--; } void list_insert(list* l, int x, pt y) { //printf("inserting. %d shifts needed\n", l->n - x); if (l->n == l->s) { l->s *= 2; l->a = realloc(l->a, sizeof(pt)*l->s); } int i; for (i = l->n; i > x; i--) l->a[i] = l->a[i - 1]; l->a[x] = y; l->n++; }