hdu 3264 Open-air shopping malls 计算几何 相交圆的总面积 二分

hdu 3264 Open-air shopping malls 计算几何 相交圆的面积 二分

枚举每个点作为雨伞圆心，二分雨伞半径长度即可

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=3264

#include <stdio.h>
#include <math.h>

#define pi acos(-1.0)

struct Circle{
    double x,y,r;
};

Circle a[25];
int n;

double dist(double x1,double y1,double x2,double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

double Insertion_circle_area(Circle a1,Circle a2){
    double d_c = dist(a1.x,a1.y,a2.x,a2.y);
    if(d_c>=a1.r+a2.r) return 0;
    if(d_c <=fabs(a1.r-a2.r)){
        double temp_r = a1.r < a2.r ? a1.r : a2.r;
        return temp_r * temp_r * pi ;
    }
    double ang1 = acos((a1.r*a1.r+d_c*d_c-a2.r*a2.r)/a1.r / d_c / 2.0);
    double ang2 = acos((a2.r*a2.r+d_c*d_c-a1.r*a1.r)/a2.r / d_c / 2.0);
    return ang1 * a1.r * a1.r + ang2 * a2.r * a2.r - d_c * a1.r * sin(ang1);
}

void solve(){
    double left , right ,mid ,ans = 10000000;
    for(int i=0;i<n;i++){
        Circle temp = a[i];
        left = 0;right = 100000;
        for(int k=0;k<100;k++){
            mid = ( left + right ) / 2.0; 
            temp.r = mid;
            int flag = 0;
            for(int j=0;j<n;j++){
                if(Insertion_circle_area(temp,a[j])<a[j].r*a[j].r*pi/2.0){
                    flag = 1;
                }
            }
            if(flag)left = mid;
            else right = mid;
        }
        if(mid < ans)
            ans = mid;
    }
    printf("%.4lf\n",ans);
}

void input(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%lf %lf %lf",&a[i].x,&a[i].y,&a[i].r);
        }
        solve();
    }
}

void File(){
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
}

int main(void){
    //File();
    input();
    return 0;
}