[POJ][3831][计算几何] Open-air shopping malls

前言

又是一道看完题就立马产生思路的水题，不过计算几何都是无比麻烦的，忍了好久终于下定决心要AC了它。忍了好久！

题目大意

平面上有n个圆，给定他们各自的圆心和半径。保证任意两个圆不会互相重叠。现在求一个大圆，他的圆心与某个给定圆的圆心重合，且对于每一个给定的圆，大圆至少覆盖该圆面积的一半。求出满足要求的大圆的最小半径。

思路

枚举每个圆心，利用二分搜索最小半径。

代码

计算几何做得少，相关的命名很不规范，因为在很多地方我就是用中文也很难表达自己的思想，更别说只用一个单词来描述一个方法或变量了。

#include
#include
using namespace std;
#define pi 3.1415926535897932
struct point
{
    int x,y,r;
}malls[20];
int n;
double dis(double x1,double y1,double x2,double y2)
//（x1，y1）到（x2，y2）的距离 
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double get_area(double a,double b,double c)
{
    double acos_t=acos((a*a+b*b-c*c)/(2*a*b));
    return b*b*acos_t-b*b*sin(acos_t*2)/2;
}
bool check(int x,int y,double r)
//判断以圆x为的圆心为圆心，半径为r的圆能否覆盖圆y一半面积。 
{
    double d=dis(malls[x].x,malls[x].y,malls[y].x,malls[y].y);
    if(d>=r+malls[y].r)
    //若两圆不相交 
        return false;
    if(d<=fabs(r-malls[y].r))
    //若一个圆包含另一个圆 
        if(r>malls[y].r)
        //若当前半径为r的圆包含圆y 
            return true;
        else if(r*r*2>=malls[y].r*malls[y].r)
        //若圆y包含半径为r的圆，且覆盖面积不小于圆y的一半。 
            return true;
        else
            return false;
    //两圆相交时 
    double area=get_area(d,r,malls[y].r)+get_area(d,malls[y].r,r);
    return area-malls[y].r*malls[y].r*pi/2>=0?true:false; 
}
double find_r(int x,int y)
//寻找以圆x为的圆心为圆心，覆盖圆y至少一半面积的圆的最小半径。 
{
    double low=0,high=40000;
    while(high-low>1e-6)
    {
        double mid=(low+high)/2;
        if(check(x,y,mid))
            high=mid;
        else
            low=mid;
    }
    return low;
}
double solved(int x)
//寻找以圆x的圆心为圆心，覆盖所有圆至少一半面积的最小半径。 
{
    double max=0;
    for(int i=0;it?max:t;
    }
    return max;
}
int main()
{
    int t;
    for(scanf("%d",&t);t>0;t--)
    {
        scanf("%d",&n);
        for(int i=0;i

附上题目作者的标程：

#include
#include
#include
using namespace std;
const int MAXN=50;
const double PI=3.1415926535897932;
const double ZERO=1e-8;
int n;
double x[MAXN],y[MAXN],r[MAXN];
void init()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lf%lf%lf",&x[i],&y[i],&r[i]);
}
double dis(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double fusiform(double a,double c,double b)
{
    double angle=acos((a*a+b*b-c*c)/(2*a*b))*2;
    double s1=a*a*PI*(angle/(2*PI));
    double s2=a*a*sin(angle)/2;
    return s1-s2;
}
bool common(double x1,double y1,double r1,double x2,double y2,double r2)
{
    double d=dis(x1,y1,x2,y2);
    if(d+ZERO>=r1+r2)
        return false;
    if(d-ZERO<=fabs(r1-r2))
    {
        if(r1>r2)
            return true;
        else if(r1*r1*2+ZERO>=r2*r2)
            return true;
        else
            return false;
    }
    double value=fusiform(r1,r2,d)+fusiform(r2,r1,d);
    if(value*2>=r2*r2*PI)
        return true;
    else
        return false;
}
bool check(double ox,double oy,double rr)
{
    for(int i=1;i<=n;i++)
        if(!common(ox,oy,rr,x[i],y[i],r[i]))
            return false;
    return true;
}
double calc(double ox,double oy)
{
    double l=0,r=50000,mid,value;
    while(r-l>1e-6)
    {
        mid=(l+r)/2;
        if(check(ox,oy,mid))
            r=mid;
        else
            l=mid;
    }
    return l;
}
void work()
{
    double ans,value;
    ans=1e+10;
    for(int i=1;i<=n;i++)
    {
        value=calc(x[i],y[i]);
        if(ans>value)
            ans=value;
    }
    printf("%.4lf\n",ans);
}
int main()
{
    int t;
    for(scanf("%d",&t);t>0;t--)
    {
        init();
        work();
    }
}

后记


又是一道前前后后三天才AC的题，但是09年宁波赛区有一半的队伍现场就切了这道水题。
相比于大一刚接触ACM时能用一整天思考一道trick，现在连模拟题都懒得想。对于这种麻烦的题更是没有调试的心思，find(x,i)写成了find(i,x)，这么个小bug找了2天有余...
为什么这么浮躁？大概还是太急功近利了吧。大一时从不想着拿什么奖，只是喜欢切题。现在一门心思想拿奖，做题反而成了负担，遇到题就想尽快AC掉而不是好好思考。
看来近期得努力让自己放松下来才行，唉~

发表回复取消回复