【bzoj2961】 共点圆

http://www.lydsy.com/JudgeOnline/problem.php?id=2961 (题目链接)

题意

　　按照一定的顺序给出一些圆和一些点，对于每一个点问是否在所有圆内。

Solution

　　我算是明白计算几何题是有多蛋疼了。

　　圆包含点$(x_0,y_0)$的条件：$$x*x+y*y>=(x-x_0)*(x-x_0)+(y-y_0)*(y-y_0)$$

$$-2x_0+x_0^2+y_0^2<=2y_0y$$

　　题目只说圆心的纵坐标大于$0$，气的我吐出一口老血。所以根据$y_0$的正负，分类讨论，每种情况都是一个半平面，直线的斜率为$-x_0/y_0$，然后我们维护一个上凸包和一个下凸包对询问进行更新，CDQ分治求解就可以了。

细节

　　各种细节蛋疼死了，横坐标相等斜率特判，而且是有向线段的斜率两个点的顺序不能乱写。一开始还把斜截式写成了一般式搞了半天我就说怎么不对。

代码

// bzoj2961

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define LD long double

#define inf 1e40

#define eps 1e-10

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)

using namespace std;

const int maxn=500010;

int n,qu[maxn],st[maxn],ans[maxn];

struct data {LD x,y,k;int op,id;}q[maxn],nq[maxn];

bool cmpk(data a,data b) {return a.k<b.k;}

bool cmpid(data a,data b) {return a.id<b.id;}

LD slope(data a,data b) {

	return fabs(a.x-b.x)<=eps ? inf*(a.y<b.y ? 1 : -1) : (b.y-a.y)/(b.x-a.x);  //mdzz一定要写a.y<b.y而不是a.y>b.y,有向线段

}

LD dis(int x,int y) {

	return (q[x].x-q[y].x)*(q[x].x-q[y].x)+(q[x].y-q[y].y)*(q[x].y-q[y].y);

}

void solve(int l,int r) {

	if (l==r) return;

	int mid=(l+r)>>1,l1=l,l2=mid+1,top=0,h=1,t=0;

	for (int i=l;i<=r;i++) q[i].id<=mid ? nq[l1++]=q[i] : nq[l2++]=q[i];

	for (int i=l;i<=r;i++) q[i]=nq[i];

	solve(l,mid);

	for (int i=l;i<=mid;i++) if (!q[i].op) {

			while (top>1 && slope(q[st[top-1]],q[st[top]])<slope(q[st[top]],q[i])+eps) top--;

			st[++top]=i;

			while (h<t && slope(q[qu[t-1]],q[qu[t]])>slope(q[qu[t]],q[i])-eps) t--;

			qu[++t]=i;

		}

	for (int i=mid+1;i<=r;i++) if (q[i].op) {

			if (q[i].y<0) {

				while (top>1 && slope(q[st[top-1]],q[st[top]])<q[i].k) top--;

				if (top) ans[q[i].id]&=(dis(i,st[top])<=dis(st[top],0)+eps);   //判断条件一定要加

			}

			else {

				while (h<t && slope(q[qu[h]],q[qu[h+1]])<q[i].k) h++;

				if (h<=t) ans[q[i].id]&=(dis(i,qu[h])<=dis(qu[h],0)+eps);   //判断条件一定要加

			}

		}

	solve(mid+1,r);

	for (int i=l,j=mid+1,k=l;i<=mid || j<=r;) {

		if (j>r || (i<=mid && q[i].x<q[j].x)) nq[k++]=q[i++];

		else nq[k++]=q[j++];

	}

	for (int i=l;i<=r;i++) q[i]=nq[i];

}

int main() {

	scanf("%d",&n);

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

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

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

		ans[i]=1;q[i].id=i;

	}

	sort(q+1,q+1+n,cmpk);

	solve(1,n);

	sort(q+1,q+1+n,cmpid);

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

		if (q[i].op) puts(flag && ans[q[i].id] ? "Yes" : "No");

		else flag=1;

	}

	return 0;

}