转载请注明出处,谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526
by---cxlove
题目:就是求多边形的费马点,输出最小的距离。
http://poj.org/problem?id=2420
做法:随机化变步长贪心法(模拟退火???)
首先随机选出一点,我直接取了0,0
然后选定一个步长,往4个方向开始找,如果更优则继续,否则降低步长,直到满足题目要求精度
也可以8个方向等等
#include<iostream>
#include<fstream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<sstream>
#include<cassert>
#define LL long long
#define eps 1e-6
#define inf 1ll<<50
#define zero(a) fabs(a)<eps
#define N 20005
using namespace std;
struct Point{
double x,y;
}p[105],cur,pre;
int n;
int way[4][2]={0,1,0,-1,1,0,-1,0};
double dist(Point p1,Point p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double get_dist(Point cen){
double sum=0;
for(int i=0;i<n;i++)
sum+=dist(cen,p[i]);
return sum;
}
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
pre.x=0;pre.y=0;
double step=100,best=get_dist(pre);
while(step>0.2){
bool ok=true;
while(ok){
ok=false;
for(int i=0;i<4;i++){
cur.x=way[i][0]*step+pre.x;
cur.y=way[i][1]*step+pre.y;
double dis=get_dist(cur);
if(dis<best){best=dis;pre=cur;ok=true;}
}
}
step/=2.0;
}
printf("%d\n",(int)(best+0.5)*100/100);
}
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分类