cf 744D

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

给你红点蓝点，找一个最大的圆，圆里没有蓝点并且至少有一个红点。边界可算可不算。

一开始没看懂题解，想了好久(一整天)才想明白是枚举弦上点二分半径check角度，看了下clj的代码发现思路都一样就开始写了。

借鉴了一下clj的代码。

调了一个多小时。

几个注意点：看到好多 random_shuffle 的，我没有，也感觉没什么必要。(另外cjl的代码去掉random_shuffle好像会WA。。。)

极角排序之后可能会遇到很多很多点全在一个角上，这个时候如果排序的话会麻烦，比方说我们要先减后加(哪里麻烦了啊？？？)

所以我每次check是不是扫完了完整的一段，也可以理解成我们扫角度不扫点。

小优化，每次二分先check ans，然后把l设成ans。

关于怎么求角的范围：两个圆夹起来就是了，初中解析几何？

千万不要把二分的eps设成1e-8，不然你会在test5tle到自闭并且还根本不知道哪里T了。

(感冒摸了三天鱼了。不过这题收获还蛮大的)

 #include <bits/stdc++.h>

 #define rep(x) for(int i=0;i<x;i++)

 #define mk(a,b) make_pair(a,b)

 using namespace std;

 typedef double db;

 const db eps=1e-;

 const db pi=acos(-);

 int sign(db k){

     if (k>eps) return ; else if (k<-eps) return -; return ;

 }

 int cmp(db k1,db k2){return sign(k1-k2);}

 struct point{

     db x,y;

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

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

     point operator * (db k1) const{return (point){x*k1,y*k1};}

     point operator / (db k1) const{return (point){x/k1,y/k1};}

     int operator == (const point &k1) const{return cmp(x,k1.x)==&&cmp(y,k1.y)==;}

     // 逆时针旋转

     point turn(db k1){return (point){x*cos(k1)-y*sin(k1),x*sin(k1)+y*cos(k1)};}

     bool operator < (const point k1) const{

         int a=cmp(x,k1.x);

         if (a==-) return ; else if (a==) return ; else return cmp(y,k1.y)==-;

     }

     db abs(){return sqrt(x*x+y*y);}

     db abs2(){return x*x+y*y;}

     db dis(point k1){return ((*this)-k1).abs();}

     db getw(){return atan2(y,x);}

     int getP() const{return sign(y)==||(sign(y)==&&sign(x)==-);}

 };

 db cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;}

 db dot(point k1,point k2){return k1.x*k2.x+k1.y*k2.y;}

 db slove(db S){

     if(S<)S+=*pi;

     else if(S>=*pi) S-=*pi;

     return S;

 }

 point r[],b[];

 vector<point> p;

 int n,m;

 vector<pair<db,int>> g;

 bool check(int id,db R){

     g.clear();

     point o = p[id];

     rep(n+m){

         if(i==id)continue;

         point tmp = p[i];

         db d = tmp.dis(o);

         if(cmp(d,R*)>=)continue;

         db alf = acos(d//R);

         db delta = atan2(tmp.y-o.y,tmp.x-o.x);

         db l = slove(delta-alf),r=slove(delta+alf);

         if(l<r){

             g.push_back(mk(l,i<n?:));

             g.push_back(mk(r,-(i<n?:)));

         }else{

             g.push_back(mk(l,i<n?:));

             g.push_back(mk(*pi,-(i<n?:)));

             g.push_back(mk(,i<n?:));

             g.push_back(mk(r,-(i<n?:)));

         }

     }

     if(id<n)g.push_back(mk(,id<n?:)),g.push_back(mk(*pi,-(id<n?:)));

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

     int rn=,bn=;

     rep(g.size()){

         if((i==g.size()-||g[i].first!=g[i+].first)&&rn>&&bn<=)return true;

         if(abs(g[i].second)==)

             bn+=g[i].second;

         else

             rn+=g[i].second/;

     }

     return false;

 }

 //枚举弦上点，二分半径，check角度范围，判断是否可行

 int main(){

     //freopen("zibi.in","r",stdin);

     scanf("%d%d",&n,&m);

     rep(n) scanf("%lf%lf",&r[i].x,&r[i].y),p.push_back(r[i]);

     rep(m) scanf("%lf%lf",&b[i].x,&b[i].y),p.push_back(b[i]);

     bool f=;

     rep(n+m)

         if(check(i,1e15))

             //return 0*printf("%d -1\n",i);

             return *printf("-1\n");

     db ans = ;

     //random_shuffle(p.begin(),p.begin()+n);

     //random_shuffle(p.begin()+n,p.end());

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

         db l=ans,r=1e9;

         if(check(i,ans)) {

             while (l + eps < r) {

                 db mid = (l + r) / ;

                 if (check(i, mid))

                     l = mid;

                 else r = mid;

             }

             ans = l;

            // printf("%d %.11f\n",i,ans);

         }

     }

     printf("%.11f\n",ans);

 }

 /**

  */

 /**

  */