学步园

昨天看了一下Beijing Regional的题目，里面的一道计算几何有思路不过翻模板木有发现圆的相交面积怎么求，后来发现这种自己推一推就得出公式了，都是初中知识。。。果真太依赖模板不是好事。==

这一题giant umbrella的面积是单调变化的，所以可以用二分查找，我写的时候照着整数二分模板敲==居然写出了l=mid+1这种。。

还有就是eps的作用，用于解决精度问题。

这里面虽说x,y,r都是整数，不过还是直接当作double输入好了，我换成Int结果就不对，可能是转double精度问题。

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include <ctype.h>
using namespace std;
//hdu 3264

int T;
int N;
const double eps=1e-9;
class circle
{
public:
    double x;
    double y;
    double r;
//       int x;
//    int y;
//    int r;
    circle(){x=0;y=0;r=0;}
    //circle(int xx,int yy,int rr)
    circle(double xx,double yy,double rr)
    {
        x=xx;
        y=yy;
        r=rr;
    }
};
circle cir[25];
double pi=acos(-1.0);
double dis(circle r1,circle r2)
{
    double xd=r1.x-r2.x;
    double yd=r1.y-r2.y;
    return sqrt(xd*xd+yd*yd);
}
double intersection(circle c1,circle c2)
{
    double d=dis(c1,c2);
    if(d>=(c1.r+c2.r)) return 0;
    else if(d<fabs(c1.r-c2.r)) return min(pi*c1.r*c1.r,pi*c2.r*c2.r);
    else
    {
        double h=(c1.r+c2.r+d)/2.0;
        double s=sqrt(h*(h-c1.r)*(h-c2.r)*(h-d))*2.0;//三角形面积的海伦公式
        double angle1=acos((c1.r*c1.r+d*d-c2.r*c2.r)/2.0/c1.r/d);//余弦定理
        double angle2=acos((c2.r*c2.r+d*d-c1.r*c1.r)/2.0/c2.r/d);
        double s1=angle1*c1.r*c1.r;
        double s2=angle2*c2.r*c2.r;//求扇形面积
        return s1+s2-s;//inclusive and declusive principle
    }
}
bool ishalf(circle cc)
{
    double area=0;
    for(int i=0;i<N;i++)
    {
        area=intersection(cc,cir[i]);
        //cout<<"area  "<<area<<" "<<0.5*pi*cir[i].r*cir[i].r <<endl;
        if(area<0.5*pi*cir[i].r*cir[i].r)
        {
            return false;
        }
    }
    return true;

}
double binsearch(circle c)
{
    double l=0;
    double r=30000;
    double mid=0;
    while(l+eps<=r)
    {
        mid=(l+r)/2;
     //   cout<<l<<" "<<r<<" "<<mid<<endl;
        c.r=mid;
         if(ishalf(c)==false) l=mid+eps;
         else r=mid;//-eps;

    }
    //cout<<endl;
    return mid;
}
int main()
{
    freopen("input.txt","r",stdin);
    // freopen("data.txt","r",stdin);
     //freopen("out1.txt","w",stdout);
     scanf("%d",&T);
     for(int ca=1;ca<=T;ca++)
     {
         scanf("%d",&N);
         for(int i=0;i<N;i++)
         {
            // double x0,y0,r0;
             //scanf("%lf %lf %lf",&x0,&y0,&r0);
             scanf("%lf %lf %lf",&cir[i].x,&cir[i].y,&cir[i].r);//之前把%f写成了%f,结果数据读不进去，r是一个很大的值
            //scanf("%d %d %d",&cir[i].x,&cir[i].y,&cir[i].r);
             //cir[i]=circle(x0,y0,r0);
           // cout<< 0.5*pi*cir[i].r*cir[i].r<<endl;
          //cout<< cir[i].r<<endl;
         }
         double ans=0x3f3f3f3f;
         for(int i=0;i<N;i++)
         {
            // cout<<binsearch(cir[i])<<endl;
             ans=min(ans,binsearch(cir[i]));
         }
         printf("%.4f\n",ans);
     }

    return 0;
}