首页 > 代码库 > [POJ2420]A Star not a Tree?

[POJ2420]A Star not a Tree?

2024-11-27 14:29:39   203人阅读

来源：

Waterloo Local 2002.01.26

题目大意：

找出$n$个点的费马点。

思路：

模拟退火。
首先任取其中一个点（或随机一个坐标）作为基准点，每次向四周找距离为$t$的点，如果找到的点总距离更小，就把该点作为新的基准点。
每次找完后降低温度$t$，重复上述过程，直到温度$t$低于阈值$threshold$。
另外注意在POJ上double类型输出不能用%lf，只能用%f，一开始因为这个WA了好几次。

 1 #include<cmath> 2 #include<cstdio> 3 const double inf=1e9; 4 const int N=100; 5 const double threshold=1e-8,delta=0.98,initial_temperature=100; 6 const double d[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; 7 int n; 8 struct Point { 9     double x,y;10 };11 Point p[N];12 inline double sqr(const double x) {13     return x*x;14 }15 inline double dist(const Point a,const Point b) {16     return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));17 }18 inline double getsum(const Point x) {19     double ret=0;20     for(int i=0;i<n;i++) {21         ret+=dist(x,p[i]);22     }23     return ret;24 }25 int main() {26     scanf("%d\n",&n);27     for(int i=0;i<n;i++) {28         scanf("%lf%lf",&p[i].x,&p[i].y);29     }30     Point nowp=p[0];31     double ans=getsum(nowp),t=initial_temperature;32     while(t>threshold) {33         bool finished=false;34         while(!finished) {35             finished=true;36             for(int i=0;i<4;i++) {37                 Point nextp;38                 nextp.x=nowp.x+d[i][0]*t;39                 nextp.y=nowp.y+d[i][1]*t;40                 double tmp=getsum(nextp);41                 if(tmp<ans) {42                     ans=tmp;43                     nowp=nextp;44                     finished=false;45                 }46             }47         }48         t*=delta;49     }50     printf("%.0f\n",ans);51     return 0;52 }

 

[POJ2420]A Star not a Tree?


联系
我们