前言
又是一道看完题就立马产生思路的水题，不过计算几何都是无比麻烦的，忍了好久终于下定决心要AC了它。忍了好久！
题目大意
平面上有n个圆，给定他们各自的圆心和半径。保证任意两个圆不会互相重叠。现在求一个大圆，他的圆心与某个给定圆的圆心重合，且对于每一个给定的圆，大圆至少覆盖该圆面积的一半。求出满足要求的大圆的最小半径。
思路
枚举每个圆心，利用二分搜索最小半径。
代码
计算几何做得少，相关的命名很不规范，因为在很多地方我就是用中文也很难表达自己的思想，更别说只用一个单词来描述一个方法或变量了。
#include<stdio.h>
#include<cmath>
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;i<n;i++)
{
double t=find_r(x,i);
max=max>t?max:t;
}
return max;
}
int main()
{
int t;
for(scanf("%d",&t);t>0;t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%d%d",&malls[i].x,&malls[i].y,&malls[i].r);
double min=40000;
for(int i=0;i<n;i++)
{
double t=solved(i);
min=min<t?min:t;
}
printf("%.4lf\n",min);
}
}
附上题目作者的标程：
#include<iostream>
#include<stdio.h>
#include<cmath>
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掉而不是好好思考。
看来近期得努力让自己放松下来才行，唉~