POJ 3831 & HDU 3264 Open-air shopping malls（几何）

题目链接：

POJ:http://poj.org/problem?id=3831

HDU:http://acm.hdu.edu.cn/showproblem.php?pid=3264

Description

Input

Output

Sample Input

1
2
0 0 1
2 0 1

Sample Output

2.0822

Source

题意： 
给出一些圆，选择当中一个圆的圆心为圆心。然后画一个大圆。要求大圆最少覆盖每一个圆的一半面积。求最小面积。

代码例如以下：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>


using namespace std;
const double eps = 1e-8;
const double PI = acos(-1.0);

int sgn(double x)
{
    if(fabs(x) < eps) return 0;
    if(x < 0) return - 1;
    else return 1;
}
struct Point
{
    double x, y, r;
    Point() {}
    Point(double _x, double _y)
    {
        x = _x;
        y = _y;
    }
    Point operator -( const Point &b) const
    {
        return Point(x - b. x, y - b. y);
    }
    //叉积
    double operator ^ (const Point &b) const
    {
        return x*b. y - y*b. x;
    }
    //点积
    double operator * (const Point &b) const
    {
        return x*b. x + y*b. y;
    }
    //绕原点旋转角度B（弧度值），后x,y的变化
    void transXY(double B)
    {
        double tx = x,ty = y;
        x = tx* cos(B) - ty*sin(B);
        y = tx* sin(B) + ty*cos(B);
    }
};
Point p[47];

//*两点间距离
double dist( Point a, Point b)
{
    return sqrt((a-b)*(a- b));
}
//两个圆的公共部分面积
double Area_of_overlap(Point c1, double r1, Point c2, double r2)
{
    double d = dist(c1,c2);
    if(r1 + r2 < d + eps) return 0;
    if(d < fabs(r1 - r2) + eps)
    {
        double r = min(r1,r2);
        return PI*r*r;
    }
    double x = (d*d + r1*r1 - r2*r2)/(2*d);
    double t1 = acos(x / r1);
    double t2 = acos((d - x)/r2);
    return r1*r1*t1 + r2*r2*t2 - d*r1*sin(t1);
}

int main()
{
    double x1, y1, r1, x2, y2, r2;
    int t;
    int n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i = 0; i < n; i++)
        {
            scanf("%lf %lf %lf",&p[i].x,&p[i].y,&p[i].r);
        }
        double ans = 999999;
        double l, r, mid;
        for(int i = 0; i < n; i++) //枚举圆心
        {
            l = 0;
            r = 35000.0;//二分
            while(r-l > eps)//能找到
            {
                mid = (l+r)/2.0;
                int flag = 0;
                for(int j = 0; j < n; j++) // 每一个点
                {
                    if(Area_of_overlap(p[i],mid,p[j],p[j].r)<p[j].r*p[j].r*PI/2.0)
                    {
                        flag = 1;//太小
                        break;
                    }
                }
                if(flag)
                    l = mid;
                else
                    r = mid;
            }
            if(l < ans)
                ans = l;
        }
        printf("%.4lf\n",ans);
    }
    return 0;
}

本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5210854.html，如需转载请自行联系原作者