HDU 3264 Open-air shopping malls ——（二分+圆交）

　　纯粹是为了改进牛吃草里的两圆交模板= =。

　　代码如下：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <vector>

 #include <math.h>

 using namespace std;

 const int N =  + ;

 typedef long long ll;

 const double eps = 1e-;

 const double pi = acos(-1.0);

 double inf = ;

 struct circle

 {

     double x,y,r;

     void read()

     {

         scanf("%lf%lf%lf",&x,&y,&r);

     }

     double calS()

     {

         return pi*r*r;

     }

 }c[];

 double myabs(double x) {return x <  ? -x : x;}

 double get(circle c1,circle c2)

 {

     double a = c1.x, b = c1.y, R = c1.r;

     double x = c2.x, y = c2.y, r = c2.r;

     double dx = myabs(a-x), dy = myabs(b-y);

     double d = sqrt(dx*dx+dy*dy);

     if(d > R + r) return 0.0;

     if(R < r) swap(R,r);

     if(d < R-r) return pi*r*r;

     double A = 2.0*acos((R*R+d*d-r*r)/(2.0*R*d));

     double B = 2.0*acos((r*r+d*d-R*R)/(2.0*r*d));

     double s1 = 0.5*A*R*R + 0.5*B*r*r;

     double s2 = 0.5*R*R*sin(A) + 0.5*r*r*sin(B);

     return s1 - s2;

 }

 int n;

 bool solve(circle now)

 {

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

     {

         if(get(now,c[i]) >= 0.5*c[i].calS()) ;

         else return ;

     }

     return ;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         for(int i=;i<=n;i++) c[i].read();

         double ans = inf;

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

         {

             circle now = c[i];

             double L = , R = inf;

             int CNT = ;

             while(CNT--)

             {

                 double mid = (L + R) / ;

                 now.r = mid;

                 if(solve(now)) R = mid;

                 else L = mid;

             }

             ans = min(ans, R);

         }

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

     }

     return ;

 }