题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=2420
题目意思:求平面上存在的一点到多边形的各个顶点的距离和最小,即费马点。
//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()
{
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;
}
分享到:
相关推荐
北大POJ2525-Text Formalization【TrieTree】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/XW4FQ3
北大POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】 解题报告+AC代码
poj 1909 Marbles on a tree.md
poj 1308 Is It A Tree_.md
北大POJ1584-A Round Peg in a Ground Hole 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ2255-Tree Recovery 解题报告+AC代码
北大POJ2488-A Knight's Journey 解题报告+AC代码
北大POJ1942-Paths on a Grid 解题报告+AC代码
poj 2201 Cartesian Tree.md
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
Give a tree with n vertices,each edge has a length(positive integer less than 1001). Define dist(u,v)=The min distance between node u and v. Give an integer k,for every pair (u,v) of vertices is ...
北大POJ1005-I Think I Need a Houseboat 解题报告+AC代码
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
POJ1584 -A Round Peg in a Ground Hole 测试数据。数据来源 Mid-Atlantic 2003 问题D
Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars. For example, ...
北大POJ1004-Financial Management 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类