首页 > 代码库 > poj2420A Star not a Tree?(模拟退火)
poj2420A Star not a Tree?(模拟退火)
链接
求某一点到其它点距离和最小,求这个和,这个点 为费马点。
做法:模拟退火
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set>10 using namespace std;11 #define N 10000012 #define LL long long13 #define INF 0xfffffff14 const double eps = 1e-8;15 const double pi = acos(-1.0);16 const double inf = ~0u>>2;17 struct point18 {19 double x,y;20 point(double x=0,double y =0):x(x),y(y){}21 }p[N];22 int n;23 int dir[4][2] = {0,1,0,-1,1,0,-1,0};24 typedef point pointt;25 pointt operator -(point a,point b)26 {27 return point(a.x-b.x,a.y-b.y);28 }29 double dis(point a)30 {31 return sqrt(a.x*a.x+a.y*a.y);32 }33 double cal(point pp)34 {35 int i;36 double s = 0;37 for(i = 1; i <= n; i++)38 s+=dis(pp-p[i]);39 return s;40 }41 int main()42 {43 int i;44 while(scanf("%d",&n)!=EOF)45 {46 double t = 10000;47 point pp = point(0,0);48 for(i =1 ; i <= n;i ++)49 {50 scanf("%lf%lf",&p[i].x,&p[i].y);51 pp.x+=p[i].x;52 pp.y+=p[i].y;53 }54 pp.x /=n;55 pp.y /=n;56 double sum = cal(pp),tmp;57 point tp,ans = pp;58 while(t>0.02)59 {60 int flag = 1;61 while(flag)62 {63 flag = 0;64 for(i =0 ; i< 4 ; i++)65 {66 tp = point(pp.x+dir[i][0]*t,pp.y+dir[i][1]*t);67 tmp = cal(tp);68 if(tmp<sum)69 {70 sum = tmp;71 flag = 1;72 ans = tp;73 }74 }75 pp = ans;76 }77 t/=2;78 }79 printf("%.0f\n",sum);80 }81 return 0;82 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。