题面

bzoj

其实就是推一下圆的式子

长成这个样子

假设要查询的点是(x, y) 某个圆心是(p, q)

\((x - p)^2 + (y - q)^2 \leq p^2 + q^2\)

变成

\(-\frac{2x}{2y}p + \frac{x^2+y^2}{2y} \leq q\)

那么一个点合法就要对所有圆心都满足上面这个式子

很明显拿斜率截就好啦

然后cdq维护上下凸包

附：cdq维护凸包过程

void cdq(int L, int R){

    if(L == R) return ;

    int Mid = L + ((R - L) >> 1), tl, tr;

    按照时间分左右

    cdq(L, Mid);

    int t1 = 0, t2 = 0;

    for(int i = L; i <= Mid; ++i){

	if(node[i].type) continue;

	构造上凸包 下凸包

    }

    for(int i = Mid + 1, j1 = 1, j2 = t2; i <= R; ++i){

	if(!node[i].type) continue;

	    if(node[i].y > 0){//mdf

		根据斜率正负判断用上还是下（本题负斜率用下凸包

    }

    cdq(Mid + 1, R);

    归并，按照x排序

}

如果你wa了你要知道

这道题不可以用叉积判凸包

这道题不可以做完减法判slope

这道题不可以不加eps

我哭辽qvq

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cmath>

#include <cstring>

#define Sqr(x) ((x)*(x))

using namespace std;

const int N = 5e5 + 5;

const double eps = 1e-11;//这里1e-8到1e-11都可以

struct Node{

    int t;

	double x, y, k;

	bool type, ok;

	friend bool operator <(Node x, Node y){return fabs(x.x - y.x) < eps ? x.y < y.y : x.x < y.x;}

}node[N], stk[N], s1[N], s2[N];

int n;

double slope(Node a,Node b)

{

    if(fabs(a.x-b.x)<eps)return a.y<b.y?1e18:-1e18;

    return (a.y-b.y)/(a.x-b.x);

}

double Dis(Node a,Node b){return sqrt(Sqr(a.x-b.x)+Sqr(a.y-b.y));}//距离和斜率必须这么写！不能减后判断！

//inline double cross(Node x, Node y){return x.x * y.y - x.y * y.x;}

bool rule_t(Node x, Node y){return x.t < y.t;}

bool rule_k(Node x, Node y){return x.k < y.k;}

void cdq(int L, int R){

    if(L == R) return ;

	int Mid = L + ((R - L) >> 1), tl, tr;

    tl = L, tr = Mid + 1;

    for(int i = L; i <= R; ++i)

		if(node[i].t <= Mid) stk[tl++] = node[i];

		else stk[tr++] = node[i];

    for(int i = L; i <= R; ++i) node[i] = stk[i];

    cdq(L, Mid);

    int t1 = 0, t2 = 0;

    for(int i = L; i <= Mid; ++i){

		if(node[i].type) continue;

	    while(t1 > 1 && slope(s1[t1 - 1], node[i]) - eps < slope(s1[t1 - 1], s1[t1])) --t1;

		s1[++t1] = node[i];//涓嬪嚫鍖咃紙璐熸枩鐜囷級

	    while(t2 > 1 && slope(s2[t2 - 1], node[i]) + eps > slope(s2[t2 - 1], s2[t2])) --t2;//用叉积判凸包会wa！

		s2[++t2] = node[i];//涓婂嚫鍖?

	}

	for(int i = Mid + 1, j1 = 1, j2 = t2; i <= R; ++i){

	    if(!node[i].type) continue;

		if(node[i].y > 0){//mdf

		    while(j1 < t1 && slope(s1[j1], s1[j1 + 1]) < node[i].k) ++j1;

		    if(j1 <= t1 && Dis(s1[j1], s1[0]) < Dis(node[i], s1[j1])) node[i].ok = 0;

		//		printf("-------\n");s1[j1].print(); node[i].print();

		}

		else {

		    while(j2 > 1 && slope(s2[j2], s2[j2 - 1]) > node[i].k) --j2;

			if(j2 >= 1 && Dis(s2[j2], s2[0]) < Dis(node[i], s2[j2]))	node[i].ok = 0;

		  //  printf("---------\n");s2[j2].print(); node[i].print();

		}

	}

    //printf("%d %d\n", L, R);

    cdq(Mid + 1, R);

	tl = L, tr = Mid + 1, t1 = L;

	while(tl <= Mid && tr <= R)

		if(node[tl] < node[tr]) stk[t1++] = node[tl++];

		else stk[t1++] = node[tr++];

    while(tl <= Mid) stk[t1++] = node[tl++];

	while(tr <= R) stk[t1++] = node[tr++];

    for(int i = L; i <= R; ++i) node[i] = stk[i];

}

int main() {

	scanf("%d", &n);

	bool flag = 0;

	for(int i = 1; i <= n; ++i){

	    scanf("%d%lf%lf", &node[i].type, &node[i].x, &node[i].y);

		node[i].t = i;

		node[i].k = fabs(node[i].y) > eps ? -node[i].x / node[i].y :

		(node[i].x > 0 ? -1e18 : 1e18);

		if(node[i].type) node[i].ok = flag; else flag = 1;

	}

	sort(node + 1, node + n + 1, rule_k);

	cdq(1, n);

	sort(node + 1, node + n + 1, rule_t);

	for(int i = 1; i <= n; ++i){

		//printf("%d %.4lf %.4lf %d\n", node[i].type, node[i].x, node[i].y, node[i].ok);

	    if(node[i].type){

		    if(node[i].ok) printf("Yes\n");

			else printf("No\n");

		}

	}

	system("PAUSE");

    return 0;

}