首页 > 代码库 > 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 }
View Code