Mayflyyh
Mayflyyh
MayFlyyh's Blog
POJ 2420 A Star not a Tree

给定一个平面和平面上n个点求出一点到所有点的距离和最小输出该最小距离;

很想JS省选吊打XXX

答案是模拟退火,思路明白了以后,重点是每次重新选点的随机方式一定要好。这个一定要多做几道模拟退火领会一下思路。因为我发现不按照题解那样写还真不行。。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
using namespace std;
int n;
double xx,yy,ans,t;
struct point{double x,y;}p[105];
double sqr(double x){return x*x;}
double dis(double x,double y,point p)
{return sqrt(sqr(x-p.x)+sqr(y-p.y));}
double getsum(double x,double y)
{
    double tmp=0;
    for(int i=1;i<=n;i++)
        tmp+=dis(x,y,p[i]);
    return tmp;
}
int main()
{
    srand(time(0));
    while(scanf("%d",&n)!=EOF)
    {
        xx=yy=0;ans=1e20;t=100000;
        for(int i=1;i<=n;i++)
        {
            scanf("%lf%lf",&p[i].x,&p[i].y);
            xx+=p[i].x;yy+=p[i].y;
        }
        xx/=n;yy/=n;
        ans=getsum(xx,yy);
        double tmp,x,y;
        while(t>0.02)
        {
            x=y=0;
            for(int i=1;i<=n;i++)
            {
                x+=(p[i].x-xx)/dis(xx,yy,p[i]);
                y+=(p[i].y-yy)/dis(xx,yy,p[i]);
            }
            tmp=getsum(xx+x*t,yy+y*t);
            if(tmp<ans)
            {ans=tmp;xx+=x*t,yy+=y*t;}
            else if(log((tmp-ans)/t)<(rand()%10000)/10000.0)
            {ans=tmp;xx+=x*t,yy+=y*t;}       
            t*=0.9; 
        }
        printf("%.0lf\n",ans);
    }
    return 0;
}
本文链接:http://www.mayflyyh.com/archives/285
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      随机算法      POJ 2420 A Star not a Tree
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

Captcha Code

MayFlyyh's Blog

POJ 2420 A Star not a Tree
给定一个平面和平面上n个点求出一点到所有点的距离和最小输出该最小距离; 很想JS省选吊打XXX 答案是模拟退火,思路明白了以后,重点是每次重新选点的随机方式一定要好。这个一定要多…
扫描二维码继续阅读
2018-07-16