学步园

题意：N(1<=N<=20) 个圆，现取其中一个圆的圆心为圆心作一个大圆，使得这个大圆与其他任意一个圆 c 的面积交 >= c 的面积的一半，求大圆的最小半径。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3264

——>>枚举圆心，二分半径。。

#include <cstdio>
#include <cmath>
#include <algorithm>

using std::min;

const double EPS = 1e-8;
const double PI = acos(-1.0);
const int MAXN = 20 + 10;

int N;
double harea[MAXN];

int Dcmp(double x)
{
    if (fabs(x) < EPS) return 0;
    return x > 0 ? 1 : -1;
}

struct POINT
{
    double x;
    double y;

    POINT(double x = 0.0, double y = 0.0) : x(x), y(y) {}
};
typedef POINT VECTOR;

struct CIRCLE
{
    POINT c;
    double r;

    CIRCLE() {}
    CIRCLE(POINT c, double r) : c(c), r(r) {}
} mall[MAXN];

double Length(POINT A, POINT B)
{
    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

// 两圆面积交
double AreaCircleCircle(CIRCLE c1, CIRCLE c2)
{
    double ret = 0.0;
    double d = Length(c1.c, c2.c);

    if (Dcmp(d - c1.r - c2.r) < 0 && Dcmp(d - fabs(c1.r - c2.r)) > 0)
    {
        double a1 = acos((c1.r * c1.r + d * d - c2.r * c2.r) / 2 / c1.r / d);
        double a2 = acos((c2.r * c2.r + d * d - c1.r * c1.r) / 2 / c2.r / d);
        ret = (a1 - sin(2 * a1) / 2) * c1.r * c1.r + (a2 - sin(2 * a2) / 2) * c2.r * c2.r;
    }
    else if (Dcmp(d - fabs(c1.r - c2.r)) <= 0)
    {
        if (Dcmp(c1.r - c2.r) < 0)
        {
            ret = PI * c1.r * c1.r;
        }
        else
        {
            ret = PI * c2.r * c2.r;
        }
    }

    return ret;
}

void Read()
{
    scanf("%d", &N);
    for (int i = 0; i < N; ++i)
    {
        scanf("%lf%lf%lf", &mall[i].c.x, &mall[i].c.y, &mall[i].r);
        harea[i] = PI * mall[i].r * mall[i].r / 2;
    }
}

bool IsOk(const POINT& center, const double& r)
{
    for (int i = 0; i < N; ++i)
    {
        if (Dcmp(AreaCircleCircle(CIRCLE(center, r), mall[i]) - harea[i]) < 0)
        {
            return false;
        }
    }
    return true;
}

void Solve()
{
    double ret = 34000.0;

    for (int i = 0; i < N; ++i)
    {
        double L = 0.0;
        double R = 34000.0;

        while (Dcmp(L - R) < 0)
        {
            double M = (L + R) / 2;
            IsOk(mall[i].c, M) ? R = M : L = M;
        }
        ret = min(ret, L);
    }

    printf("%.4f\n", ret);
}

int main()
{
    int T;

    scanf("%d", &T);
    while (T--)
    {
        Read();
        Solve();
    }

    return 0;
}