纯粹是为了改进牛吃草里的两圆交模板= =。
代码如下：
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 ",ans); 79 } 80 return 0; 81 }