zoj 3716

题目给我们四个点,要求我们以这四个点为圆心,形成四个相切的圆;

求他们的半径和;

首先我们从他们中间选出三个点,以这三个点为圆心的三个圆最大可以两两互相相切;

证明:假设这三个圆的半径分别为a,b,c,那么形成的三条边分别长为:a+b,a+c,b+c,他们两两之和大于第三边;

然后从第四个点出发的圆必定和前面三个的一个或多个相切;

所以这个问题就转化成为三对边和的比较;

代码:

 #include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
double dis(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
double x[],y[];
while(scanf("%lf%lf",&x[],&y[])!=EOF)
{
for(int i=;i<;i++)
scanf("%lf%lf",&x[i],&y[i]);
double d1=dis(x[],y[],x[],y[]);
double d2=dis(x[],y[],x[],y[]);
double d3=dis(x[],y[],x[],y[]);
double d4=dis(x[],y[],x[],y[]);
double d5=dis(x[],y[],x[],y[]);
double d6=dis(x[],y[],x[],y[]);
printf("%lf\n",min(d1+d3,min(d2+d4,d5+d6)));
}
return ;
}
上一篇:VCS仿真查看coverage


下一篇:Course Selection System ZOJ - 3956 01背包+思维