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

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <vector>
 5 #include <math.h>
 6 using namespace std;
 7 const int N = 100000 + 100;
 8 typedef long long ll;
 9 const double eps = 1e-8;
10 const double pi = acos(-1.0);
11 double inf = 50000;
12 
13 struct circle
14 {
15     double x,y,r;
16     void read()
17     {
18         scanf("%lf%lf%lf",&x,&y,&r);
19     }
20     double calS()
21     {
22         return pi*r*r;
23     }
24 }c[30];
25 
26 double myabs(double x) {return x < 0 ? -x : x;}
27 
28 double get(circle c1,circle c2)
29 {
30     double a = c1.x, b = c1.y, R = c1.r;
31     double x = c2.x, y = c2.y, r = c2.r;
32     double dx = myabs(a-x), dy = myabs(b-y);
33     double d = sqrt(dx*dx+dy*dy);
34     if(d > R + r) return 0.0;
35     if(R < r) swap(R,r);
36     if(d < R-r) return pi*r*r;
37     double A = 2.0*acos((R*R+d*d-r*r)/(2.0*R*d));
38     double B = 2.0*acos((r*r+d*d-R*R)/(2.0*r*d));
39     double s1 = 0.5*A*R*R + 0.5*B*r*r;
40     double s2 = 0.5*R*R*sin(A) + 0.5*r*r*sin(B);
41     return s1 - s2;
42 }
43 
44 int n;
45 bool solve(circle now)
46 {
47     for(int i=1;i<=n;i++)
48     {
49         if(get(now,c[i]) >= 0.5*c[i].calS()) ;
50         else return 0;
51     }
52     return 1;
53 }
54 
55 int main()
56 {
57     int T;
58     scanf("%d",&T);
59     while(T--)
60     {
61         scanf("%d",&n);
62         for(int i=1;i<=n;i++) c[i].read();
63         double ans = inf;
64         for(int i=1;i<=n;i++)
65         {
66             circle now = c[i];
67             double L = 0, R = inf;
68             int CNT = 150;
69             while(CNT--)
70             {
71                 double mid = (L + R) / 2;
72                 now.r = mid;
73                 if(solve(now)) R = mid;
74                 else L = mid;
75             }
76             ans = min(ans, R);
77         }
78         printf("%.4f\n",ans);
79     }
80     return 0;
81 }