CF744DHongcow Draws a Circle
题意: 给你平面上 n 个红点和 m 个蓝点, 求一个最大的圆, 满足圆内不存在蓝点, 且至少包含一个红点
$n,m\le 10^3$
题解: 我们先不考虑半径为 inf 的情况显然所求的圆一定是要与某个蓝点相切的我们可以先枚举这个蓝点, 然后二分答案当半径已知一个点固定时, 圆的可能位置只能是绕着一个点旋转得到的结果, 其余的所有点都对应着极角上的一段区间, 我们可以将这些区间排序, 采用扫描线, 看一下是否存在一段区间包含红点且不包含蓝点即可
但是如果你仔细分析的话你会发现这样的二分是不满足单调性的不过如果我们一开始不光枚举蓝点, 还枚举所有红点, 一起进行二分, 这样就满足单调性了
直接做的复杂度是 $O(n\log ^2 n)$, 会 TLE, 看了标程加了一些神优化才过~ 具体见代码
- #include <cstdio>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- #include <cmath>
- #define pi acos(-1.0)
- using namespace std;
- typedef long double db;
- const db eps=1e-12;
- const int maxn=1010;
- struct point
- {
- db x,y;
- point() {}
- point(db a,db 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);}
- db operator * (const point &a) const {return x*a.y-y*a.x;}
- point operator * (const db &a) const {return point(x*a,y*a);}
- }p[maxn<<1];
- struct line
- {
- point p,v;
- line() {}
- line(point a,point b) {p=a,v=b;}
- };
- struct node
- {
- db x;
- int k;
- node() {}
- node(double a,int b) {x=a,k=b;}
- }q[maxn<<3];
- int n,m,tot;
- inline db dis(point a,point b)
- {
- return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
- }
- db getrange(point a,point b,db R)
- {
- db d=dis(a,b)/2;
- return acos(d/R);
- }
- bool cmp(const node &a,const node &b) {return a.x<b.x;}
- inline bool solve(int x,db R)
- {
- int i;
- tot=0;
- if(x<=n) q[++tot]=node(-pi,1),q[++tot]=node(pi,-1);
- else
- {
- for(i=1;i<=n;i++)
- {
- if(dis(p[i],p[x])>R+R-eps) continue;
- db a=getrange(p[x],p[i],R),b=atan2(p[i].y-p[x].y,p[i].x-p[x].x);
- db c=b-a,d=b+a;
- if(c<-pi) c+=2*pi;
- if(d>pi) d-=2*pi;
- if(c<d) q[++tot]=node(c,1),q[++tot]=node(d,-1);
- else q[++tot]=node(-pi,1),q[++tot]=node(d,-1),q[++tot]=node(c,1),q[++tot]=node(pi,-1);
- }
- }
- for(i=n+1;i<=n+m;i++)
- {
- if(dis(p[i],p[x])>R+R-eps) continue;
- db a=getrange(p[x],p[i],R),b=atan2(p[i].y-p[x].y,p[i].x-p[x].x);
- db c=b-a,d=b+a;
- if(c<-pi) c+=2*pi;
- if(d>pi) d-=2*pi;
- if(c<d) q[++tot]=node(c,-10000),q[++tot]=node(d,10000);
- else q[++tot]=node(-pi,-10000),q[++tot]=node(d,10000),q[++tot]=node(c,-10000),q[++tot]=node(pi,10000);
- }
- sort(q+1,q+tot+1,cmp);
- int tmp=0;
- for(i=1;i<=tot;i++)
- {
- if(tmp>0&&i!=1&&q[i].x>q[i-1].x+eps) return 1;
- tmp+=q[i].k;
- }
- return 0;
- }
- inline bool check(db mid)
- {
- for(int i=1;i<=n+m;i++) if(solve(i,mid)) return 1;
- return 0;
- }
- 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;
- }
- int main()
- {
- n=rd(),m=rd();
- if(m==1)
- {
- puts("-1");
- return 0;
- }
- int i;
- for(i=1;i<=n;i++) p[i].x=rd(),p[i].y=rd();
- random_shuffle(p+1,p+n+1);
- for(i=1;i<=m;i++) p[i+n].x=rd(),p[i+n].y=rd();
- random_shuffle(p+n+1,p+m+1);
- db l=0,r,mid;
- for(i=1;i<=n+m;i++) if(solve(i,l)) // 神优化
- {
- r=1e9;
- while(r-l>1e-5)
- {
- mid=(l+r)/2;
- if(solve(i,mid)) l=mid;
- else r=mid;
- }
- }
- if(l>1e9-1) puts("-1");
- else printf("%.18Lf",l);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2514691.html