hdu 3265 Posters

hdu 3265 Posters

///給你若干個沒有交集的圓，以其中一個圓的圓心為圓心做一個圓
///使得這個圓至少包含所有圓面積的一半，求這個圓最小的半徑
# include 
# include 
# include 
# include 
# include 
#include 
using namespace std;
struct node
{
    double x;
    double y;
    double r;
};
int t1,t2;
double rr;
const double d = 1e-10;
const double pi = acos(-1.0);
struct node a[25];
double ss;
double cal(int x1,int y1)///兩圓圓心距離
{
    return sqrt((a[x1].x-a[y1].x)*(a[x1].x-a[y1].x)*1.0+(a[x1].y-a[y1].y)*(a[x1].y-a[y1].y)*1.0);
}
double area(double mid)///求兩圓交叉面積
{
    double a = cal(t1, t2), b = rr, c = mid;
    double cta1 = acos((a * a + b * b - c * c) / 2 / (a * b)),
           cta2 = acos((a * a + c * c - b * b) / 2 / (a * c));
    double s1 = rr*rr*cta1 - rr*rr*sin(cta1)*(a * a + b * b - c * c) / 2 / (a * b);
    double s2 = mid*mid*cta2 - mid*mid*sin(cta2)*(a * a + c * c - b * b) / 2 / (a * c);
    return s1 + s2;
}
double f(double m)
{
    if(area(m)-ss>=1e-20)
        return 1;
    else
        return 0;
}
int main()
{
    int t,n,i,j;
    double min1,max1,min2,max2,jj;
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            scanf("%d",&n);
            for(i=0; id)///二分面積
                            {
                                double  mid=(l+r)/2;
                                if(f(mid)==1)
                                    r=mid;
                                else
                                    l=mid;
                            }
                            ll=max(ll,l);
                        }

                    }
                    lll=min(lll,ll);
                }
                printf("%.4lf\n",lll);

            }
        }
    }
    return 0;
}