题面

BZOJ传送门

思路

首先考虑一个点$(x_0,y_0)$什么时候在一个圆$(x_1,y_1,\sqrt{x_1^2+y_12})$内

显然有：$x_1^2+y_12\geq (x_0-x_1)^2+(y_0-y_1)2$

化简：$2x_0x_1+2y_0y_1\geq x_0^2+y_02$

所有含$x_1,y_1$的项挪到同一边，除掉一个$2y_0$（假设它是正的），得到：

$y_1\geq -\frac{x_0}{y_0}x_1+\frac{x_0^2+y_02}{2y_0}$

如果是负的：

$y_1\leq -\frac{x_0}{y_0}x_1+\frac{x_0^2+y_02}{2y_0}$

DUANG！半平面来了

那么现在的询问变成了：给定一个半平面，问是不是所有的点都在这个半平面的上方（或者下方）

显然，我们如果维护了所有输入节点的上下凸包，这个问题就迎刃而解了

众所周知，维护动态上下凸壳可以用$set$或者平衡树做到$O(n\log n)$

然而博主并不想写这种东西

所以他写了非常沙雕的cdq分治23333

分治

分治开始之前先按照所有询问点的斜率排个序（非询问点不管）

我们对时间顺序分治

进入分治后，首先分治左区间，返回按照横坐标排好序的左区间所有点

求出左区间中所有非询问的点的上下凸壳

然后对右边的所有询问，因为一开始排好序了，所以直接在凸壳上顺次双指针过去

注意：$y_0 > 0$的时候所有点在直线上方，用的是下凸包，反之亦然

最后分治右区间，按照x坐标归并排序，合并左右区间

就是个很模板的cdq斜率分治

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cassert>

#include<cmath>

#define sqr(x) ((x)*(x))

#define eps 1e-10

#define ll long long

using namespace std;

inline int read(){

	int re=0,flag=1;char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-') flag=-1;

		ch=getchar();

	}

	while(isdigit(ch)) re=(re<<1)+(re<<3)+ch-'0',ch=getchar();

	return re*flag;

}

struct node{

	double x,y,k;

	int id,qid,op;

	inline friend double slope(const node &a,const node &b){return ((fabs(a.x-b.x)<eps)?(1e30):((a.y-b.y)/(a.x-b.x)));}

	inline friend double dis(const node &a,const node &b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}

	inline friend double rad(const node &a){return sqrt(sqr(a.x)+sqr(a.y));}

}a[500010],tmp[500010],q1[500010],q2[500010];//q1 up q2 down

int n,top1,top2;bool ans[500010];

inline bool cmp(const node &a,const node &b){return a.k<b.k;}

void solve(int l,int r){

	if(l==r) return;

	int i,t1,t2,mid=(l+r)>>1;

	t1=l;t2=mid+1;

	for(i=l;i<=r;i++){

		if(a[i].id<=mid) tmp[t1++]=a[i];

		else tmp[t2++]=a[i];

	}

	memcpy(a+l,tmp+l,sizeof(node)*(r-l+1));

	solve(l,mid);

	top1=top2=0;

	for(i=l;i<=mid;i++){

		if(a[i].op) continue;

		while(top1>1&&slope(q1[top1-1],q1[top1])<slope(q1[top1],a[i])+eps) top1--;

		q1[++top1]=a[i];

		while(top2>1&&slope(q2[top2-1],q2[top2])+eps>slope(q2[top2],a[i])) top2--;

		q2[++top2]=a[i];

	}

	t1=t2=1;

	for(i=mid+1;i<=r;i++){

		if(!a[i].op) continue;

		if(a[i].y>0){

			while(t2<top2&&slope(q2[t2],q2[t2+1])<a[i].k) t2++;

			if(t2<=top2) ans[a[i].qid]&=(dis(a[i],q2[t2])<rad(q2[t2]));

		}

		else{

			while(t1<top1&&slope(q1[top1-1],q1[top1])<a[i].k) top1--;

			if(t1<=top1) ans[a[i].qid]&=(dis(a[i],q1[top1])<rad(q1[top1]));

		}

	}

	solve(mid+1,r);

	t1=l;t2=mid+1;

	for(i=l;i<=r;i++){

		if(t2==r+1||(t1<=mid&&a[t1].x<a[t2].x)) tmp[i]=a[t1++];

		else tmp[i]=a[t2++];

	}

	memcpy(a+l,tmp+l,sizeof(node)*(r-l+1));

}

int main(){

	n=read();int i,flag=0,cntq=0;

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

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

		a[i].id=i;

		if(a[i].op){

			a[i].qid=++cntq;

			if(flag) ans[cntq]=1;

			if(a[i].y) a[i].k=-a[i].x/a[i].y;

			else a[i].k=1e30;

		}

		else flag=1;

	}

	sort(a+1,a+n+1,cmp);

	solve(1,n);

	for(i=1;i<=cntq;i++) puts(ans[i]?"Yes":"No");

}