【CF887E】Little Brother 二分+几何

【CF887E】Little Brother

题意：给你n个圆和一条线段，保证圆和圆、圆和线段所在直线不相交，不相切，不包含。求一个过线段两端点的圆，满足不和任何圆相交（可以相切、包含）。问圆的最小半径。

n<=100000

题解：比较显然的二分题。由于新圆的半径一定在线段的中垂线上，且距离越远半径越大。那么问题就变成了最小化半径到线段的距离。

不难发现，对于每个圆来说，如果新圆不和它相交，那么半径所在的区域会被限定在$(-\infty,a]\bigcup[b,\infty)$里。a和b我们可以通过二分求得。最后用扫描线统计出所有合法的半径区间，并更新答案即可。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <cmath>

using namespace std;

const int maxn=100010;

struct point

{

	double x,y;

	point() {}

	point(double a,double b) {x=a,y=b;}

	point operator + (const point &a) const {return point(x+a.x,y+a.y);}

	point operator - (const point &a) const {return point(x-a.x,y-a.y);}

	point operator * (const double &a) const {return point(x*a,y*a);}

	double operator * (const point &a) const {return x*a.y-y*a.x;}

}A,B,P,C,D,O,K,K1;

int n,m,sum;

double R,ans;

struct node

{

	double x;	int k;

	node() {}

	node(double a,int b) {x=a,k=b;}

}q[maxn<<1];

inline double dis(point a) {return sqrt(a.x*a.x+a.y*a.y);}

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+(gc^'0'),gc=getchar();

	return ret*f;

}

bool cmp(const node &a,const node &b)

{

	return a.x<b.x;

}

int main()

{

	double l,r,mid;

	A.x=rd(),A.y=rd(),B.x=rd(),B.y=rd(),n=rd(),C=(A+B)*0.5,K=B-A;

	K=K*(1.0/dis(K)),K1=point(-K.y,K.x);

	int i,j,flag;

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

	{

		P.x=rd(),P.y=rd(),R=rd();

		flag=((P-A)*(B-P)>0);

		l=-1e12,r=1e12;

		for(j=1;j<=80;j++)

		{

			mid=(l+r)/2,O=C+(K1*mid);

			if((dis(P-O)>dis(A-O)+R)^flag)	l=mid;

			else	r=mid;

		}

		q[++m]=node(l,flag?-1:1);

		l=-1e12,r=1e12;

		for(j=1;j<=80;j++)

		{

			mid=(l+r)/2,O=C+(K1*mid);

			if((dis(A-O)>dis(P-O)+R)^flag)	r=mid;

			else	l=mid;

		}

		q[++m]=node(r,flag?1:-1);

	}

	q[++m]=node(1e12,0),q[++m]=node(-1e12,0),q[++m]=node(0,0);

	sort(q+1,q+m+1,cmp);

	ans=1e12;

	for(flag=0,i=1;i<=m;i++)

	{

		if(!sum)	flag=1,ans=min(ans,fabs(q[i].x));

		sum+=q[i].k;

		if(!sum)	flag=1,ans=min(ans,fabs(q[i].x));

	}

	if(!flag)	puts("-1");

	else	O=C+(K1*ans),printf("%.10lf",dis(A-O));

	return 0;

}//2 4 7 13 3 3 0 1 12 4 2 -4 14 2