題目：給定n個圓，需要在某個圓的圓心做一個大圓，使得大圓至少所有給定的一半面積，求出大圓的最小半徑。 分析：計算幾何、二分。此題本質是求解圓的相交面積。直接利用相交面積求解比較困難，而且會出現精度問題。由於規模較小，所以直接枚舉圓心，二分半徑求解。對於圓相交面積的求法：方法1.利用圓的方程聯立二元二次方程組，求解交點，求解交點間距離，利用余弦定理和海倫公式，求解出兩個拱形面積加和；精度會出現問題，而且會出現數據溢出。方法2：求出圓心距離，利用菱形面積和正弦定理列出面積等式，求解交點間距離，然後利用余弦定理求出兩扇形面積減去菱形面積；計算次數較多，精度會出現問題。方法3：求出圓心距離，利用余弦定理直接求出兩個扇行面積加和後減去三角形面積即可。這裡使用方法3。 注意：精度控制。 [cpp] #include <stdio.h> #include <stdlib.h> #include <math.h> typedef struct point { double x,y; }point; point P[ 25 ]; double r[ 25 ]; double cxcarea( point a, point b, double r1, double r2 ) { double dc = sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); double r = r1<r2?r1:r2; double R = r1>r2?r1:r2; if ( dc-1e-8 > r+R ) return 0.0; if ( dc+1e-8 < R-r ) return acos(-1.0)*r*r; double a1 = acos((r*r+dc*dc-R*R)/(2.0*r*dc)); double a2 = acos((R*R+dc*dc-r*r)/(2.0*R*dc)); return a1*r*r+a2*R*R-dc*r*sin(a1); } int cover( int n, double R ) { for ( int i = 1 ; i <= n ; ++ i ) { int flag = 1; for ( int j = 1 ; j <= n ; ++ j ) { double s1 = cxcarea( P[i], P[j], R, r[j] ); double s2 = acos(-1.0)*r[j]*r[j]; if ( s1*2.0 < s2 ) { flag = 0; break; } } if ( flag ) return 1; } return 0; } double b_search( int n ) { double l = 0.0,r = 50000.0,m; while ( r-l > 1e-8 ) { m = (l+r)/2.0; if ( cover( n, m ) ) r = m; else l = m; } return r; } int main() { int T,N; while ( scanf("%d",&T) != EOF ) while ( T -- ) { scanf("%d",&N); for ( int i = 1 ; i <= N ; ++ i ) scanf("%lf%lf%lf",&P[i].x,&P[i].y,&r[i]); printf("%.4lf\n",b_search(N)); } }
