bzoj2961 共点圆 （CDQ分治， 凸包）

/*
可以发现可行的圆心相对于我们要查询的点是在一个半平面上， 然后我们要做的就是动态维护凸壳然后用这个半平面去切它
看看是否是在合法的那一面然后cdq分治就可以了代码基本是抄的，*/#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<iostream>
#include<cmath>
#define ll long long
#define M 500050
#define mmp make_pair
using namespace std;
int read() {int nm = 0, f = 1;char c = getchar();for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';return nm * f;
}
const double inf = pow(2, 80), eps = 1e-10;
int q1[M], q2[M], ans[M], tot, flag, n;
struct Vec {double x, y;
};
struct Note {Vec x;int op, id, qid;double k;bool operator < (const Note &b) const {return this->k < b.k;}
} e[M], tmp[M];double sqr(double x) {return x * x;
}double slope(Vec a, Vec b) {if(fabs(a.x - b.x) < eps) return inf;return (b.y - a.y) / (b.x - a.x);
}double dis(Vec a, Vec b) {return sqr(a.x - b.x) + sqr(a.y - b.y);
}double R(Vec a) {return sqr(a.x) + sqr(a.y);
}void cdq(int l, int r) {if(l == r) return;int mid = (l + r) >> 1, p1 = l, p2 = mid + 1, h1 = 1, h2 = 1, t1 = 0, t2 = 0;for(int i = l; i <= r; i++) {if(e[i].id <= mid) tmp[p1++] = e[i];else tmp[p2++] = e[i];}memcpy(e + l, tmp + l, sizeof(e[0]) * (r - l + 1));cdq(l, mid);for(int i = l; i <= mid; i++) {if(e[i].op) continue;while(h1 < t1 && slope(e[q1[t1]].x, e[i].x) < slope(e[q1[t1 - 1]].x, e[q1[t1]].x)) t1--;q1[++t1] = i;while(h2 < t2 && slope(e[q2[t2]].x, e[i].x) > slope(e[q2[t2 - 1]].x, e[q2[t2]].x)) t2--;q2[++t2] = i;}for(int i = mid + 1; i <= r; i++) {if(!e[i].op) continue;if(e[i].x.y > 0) {while(h1 < t1 && slope(e[q1[h1]].x, e[q1[h1 + 1]].x) < e[i].k) h1++;if(h1 <= t1 && dis(e[q1[h1]].x, e[i].x) > R(e[q1[h1]].x)) ans[e[i].qid] = 0;} else {while(h2 < t2 && slope(e[q2[t2 - 1]].x, e[q2[t2]].x) < e[i].k) t2--;if(h2 <= t2 && dis(e[q2[t2]].x, e[i].x) > R(e[q2[t2]].x)) ans[e[i].qid] = 0;}}cdq(mid + 1, r);p1 = l, p2 = mid + 1;for(int i = l; i <= r; i++) {if(p2 > r || p1 <= mid && e[p1].x.x < e[p2].x.x) tmp[i] = e[p1++];else tmp[i] = e[p2++];}memcpy(e + l, tmp + l, sizeof(e[0]) * (r - l + 1));
}
int main() {n = read();for(int i = 1; i <= n; i++) {e[i].op = read();scanf("%lf%lf", &e[i].x.x, &e[i].x.y);e[i].id = i;if(e[i].op) {e[i].qid = ++tot;if(flag) ans[tot] = 1;if(e[i].x.y) e[i].k = -e[i].x.x / e[i].x.y;else e[i].k = inf;} else flag = 1;}sort(e + 1, e + n + 1);cdq(1, n);for(int i = 1; i <= tot; i++) puts(ans[i] ? "Yes" : "No");return 0;
}