【BZOJ4140】共点圆加强版（二进制分组）

题面

BZOJ

题解

我卡精度卡了一天。。。。

之前不强制在线的做法是\(CDQ\)分治，维护一个凸壳就好了。

现在改成二进制分组，每次重建凸壳就好了。。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define MAX 500500

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

#define pb push_back

struct Node{double x,y;}a[MAX];

bool operator<(Node a,Node b){if(a.x==b.x)return a.y<b.y;return a.x<b.x;}

inline double Slope(Node a,Node b)

{

	if(a.x==b.x)return a.y>b.y?1e18:-1e18;

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

}

int n,ans,top;

struct Group

{

	vector<Node> p,Q;

	int tot,tp;

	void insert(Node x){++tot;p.pb(x);}

	void clear(){p.clear();Q.clear();tot=tp=0;}

	void Build()

		{

			sort(p.begin(),p.end());

			tp=1;Q.clear();Q.pb(p[0]);

			for(int i=1;i<tot;++i)

			{

				while(tp>1&&Slope(Q[tp-1],Q[tp-2])-Slope(Q[tp-1],p[i])>=0)--tp,Q.pop_back();

				Q.pb(p[i]),++tp;

			}

		}

	bool Query(double x,double y)

		{

			double k=-x/y;int l=1,r=tp-1,ret=0;

			while(l<=r)

			{

				int mid=(l+r)>>1;

				if(k>=Slope(Q[mid],Q[mid-1]))l=mid+1,ret=mid;

				else r=mid-1;

			}

			return 2*x*Q[ret].x+2*y*Q[ret].y>=x*x+y*y;

		}

}B[50];

void insert(double x,double y)

{

	B[++top].insert((Node){x,y});

	while(top>1&&B[top].tot==B[top-1].tot)

	{

		for(int i=0;i<B[top].tot;++i)

			B[top-1].insert(B[top].p[i]);

		B[top--].clear();

	}

	B[top].Build();

}

bool Query(double x,double y)

{

	if(!top)return false;

	for(int i=1;i<=top;++i)

		if(!B[i].Query(x,y))return false;

	return true;

}

int main()

{

	scanf("%d",&n);

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

	{

		int opt;double x,y;

		scanf("%d%lf%lf",&opt,&x,&y);

		x+=ans;y+=ans;

		if(!opt)insert(x,y);

		else if(Query(x,y))++ans,puts("Yes");else puts("No");

	}

	return 0;

}