poj 3831 Open-air shopping malls
题目：给定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));
}
}
补充：软件开发 , C++ ,
