poj2420A Star not a Tree? 费马点
[cpp]题目意思:求平面上存在的一点到多边形的各个顶点的距离和最小,即费马点。
//0ms
#include<cstdio>
#include<iostream>
#include<math.h>
#define eps 1e-8
using namespace std;
const int maxn=120;
struct point{double x,y;}points[maxn],st;
int dir[4][2]={1,0,0,1,-1,0,0,-1};
int n;
double dis(point p1,point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double alldis(point tmp)
{
double sum=0;
int i;
for(i=0;i<n;i++)
{
sum+=dis(tmp,points[i]);
}
return sum;
}
double slove(double step)
{
double minn=1000000000; while(step>0.2)
{
bool isok=true;
while(isok)
{
int i;
isok=false;
for(i=0;i<4;i++)
{
point temp=st;
temp.x+=dir[i][0]*step;
temp.y+=dir[i][1]*step;
double dis=alldis(temp);
if(minn>dis)
{
isok=true;
minn=dis;
st=temp;
}
}
}
step/=2.0;
}
return minn;
}
int main()
{ www.zzzyk.com
while(~scanf("%d",&n))
{
int i;
for(i=0;i<n;i++)
scanf("%lf%lf",&points[i].x,&points[i].y);
st=points[0];
printf("%d\n",(int)(slove(1000)+0.5));
}
return 0;
}
作者:ssslpk
补充:软件开发 , C++ ,