【Codeforces 744D】Hongcow Draws a Circle
二分答案，简单计算几何
题目大意：
给定 $n$ 个红点和 $m$ 个蓝点，保证都是整点且不会有重合。要求找一个半径最大的圆，使得至少包含一个红点，但不包含蓝点（恰在圆上的点可以视为包含也可以视为不包含）。求最大的半径。无穷大输出 $-1$。
题解：
设答案为 $ans$，那么半径小于 $ans$ 的圆都是合法的答案。所以可以二分答案。
显然会有一个蓝点恰在边界上。如果没有，那么可以扩大半径直到有蓝点在边界上，这个显然更优。
那么考虑枚举边界上的蓝点，二分答案。
在 check 一个答案的时候，对每个点，计算出包含它的圆的圆心所在的极角范围（通过一些计算几何，三角函数就可以求出），然后扫描线即可，看是否存在一个极角，包含至少一个红点，不包含蓝点。时间复杂度 $O(n\log n)$（排序）。
这样做有一个很大的问题：对于一个半径 $r$，不存在一个半径为 $r$ 的点满足当前蓝点在边界上且包含红点。即没有合法的红点。但答案可能比当前 $r$ 更优。
我们先枚举红点，二分出把一个红点放在圆边界上的最大答案，这个直接二分没问题。
然后用当前答案作为二分蓝点时的最小答案，二分蓝点的答案即可。
为什么这样就不会出问题了呢？设红点答案半径为 $r$，对于一个蓝点，存在一个红点，使得包含这个蓝点和红点的最小圆的半径为 $r’$，那么若这个圆合法，则 $r\geq r’$。如果 $r<r’$，说明这个最小的圆里面有蓝点，本身不合法。
这样就避免了范围内不存在红点的情况。
时间复杂度 $O(n^2\log n\log V)$。虽然 $n$ 只有 $1000$，但是要涉及实数运算，而且二分的是实数，所以效率比较低。
有一个剪枝就是，新枚举到一个点，先 check 当前答案，如果当前答案不行，就直接跳过这个点。我们令每个点在边界上的最大答案分别为 $a_1,a_2,\dots,a_n$。上面的剪枝，当 $a$ 为升序时就会无效。
实际上，加上这个剪枝后，二分答案的次数，就是 $a$ 这个数列的最长上升子序列长度。而一个随机排列的最长上升子序列长度，是 $\log n$ 的。
所以我们对这些点random_shuffle一遍，然后加上这个剪枝即可。
期望复杂度 $O(n\log n\log V+n^2\log n)$。
Code：
#include<cstdio>
#include<algorithm>
#include<ctime>
#include<cmath>
#include<cstdlib>
using namespace std;
const int N=4005;
const double eps=1e-9,pi=acos(-1);
struct point{
int x,y;
}g[N];
int n,m;
double ans=0;
inline double dist(point a,point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
struct node{
double rd;int dlt;
inline bool operator<(const node&rhs)const{return(fabs(rd-rhs.rd)>eps?rd<rhs.rd:dlt<rhs.dlt);}
}sta[N*2];
bool check(int id,double r){
point t=g[id];
int top=0;
if(id<=n)
sta[++top]=(node){0,1},sta[++top]=(node){2*pi,-1};
else
for(int i=1;i<=n;++i){
const double d=dist(t,g[i]);
if(2*r+eps<d)continue;
double deg=acos(d/2/r);
double rgd=asin((g[i].y-t.y)/d);
if(g[i].x<t.x)rgd=pi-rgd;
double L=rgd-deg,R=rgd+deg;
if(L<0&&R<=0)L+=2*pi,R+=2*pi;
if(L<0)sta[++top]=(node){L+2*pi,1},sta[++top]=(node){2*pi,-1},L=0;
sta[++top]=(node){L,1},sta[++top]=(node){R,-1};
}
for(int i=n+1;i<=n+m;++i)
if(id!=i){
const double d=dist(t,g[i]);
if(2*r-eps<d)continue;
double deg=acos(d/2/r);
double rgd=asin((g[i].y-t.y)/d);
if(g[i].x<t.x)rgd=pi-rgd;
double L=rgd-deg,R=rgd+deg;
if(L<0&&R<=0)L+=2*pi,R+=2*pi;
if(L<0)sta[++top]=(node){L+2*pi,-10000},sta[++top]=(node){2*pi,10000},L=0;
sta[++top]=(node){L,-10000},sta[++top]=(node){R,10000};
}
sort(sta+1,sta+top+1);
sta[top+1].rd=123456;
int now=id<=n;
for(int i=1;i<=top;++i){
if(i>1&&now>0&&sta[i+1].rd-sta[i].rd>eps)return 1;
now+=sta[i].dlt;
}
return 0;
}
void work(){
for(int i=1;i<=n+m;++i)if(check(i,ans)){
int T=0;
double l=ans,r=1e9;
while(r-l>=eps){
double mid=(l+r)/2;
if(check(i,mid))l=ans=mid;else r=mid;
if(++T==128)break;
}
}
}
int main(){
srand(time(0));
scanf("%d%d",&n,&m);
for(int i=1;i<=n+m;++i)scanf("%d%d",&g[i].x,&g[i].y);
random_shuffle(g+1,g+n+1),random_shuffle(g+n+1,g+n+m+1);
work();
if(ans<=0.9e9)printf("%.11f\n",ans);else puts("-1");
return 0;
}