POJ 2420 A Star not a Tree?(模拟退火)
2024-08-23 00:56:39
居然1Y了,以前写的模拟退火很靠谱啊。
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <iostream>
using namespace std;
struct point
{
double x,y;
}p[];
int n;
int a[] = {,,-,};
int b[] = {,-,,};
double dis(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y2-y1)*(y2-y1));
}
double fun(double x,double y)
{
double ans = ;
int i;
for(i = ;i < n;i ++)
{
ans += dis(p[i].x,p[i].y,x,y);
}
return ans;
}
int main()
{
int T,i,key,num,j,k;
double tx,ty,ans,d,x,y;
srand(time(NULL));
scanf("%d",&n);
for(i = ;i < n;i ++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
}
key = ;
ans = ;
num = ;
x = p[].x;
y = p[].y;
T = ;
while(T--)
{
for(i = ;i <= num;i ++)
{
for(j = ;j < ;j ++)
{
k = rand()%key;
tx = x + k*a[j]*T;
ty = y + k*b[j]*T;
if(tx >= &&tx <= &&ty >= &&ty <= )
{
d = fun(tx,ty);
if(ans > d)
{
ans = d;
x = tx;
y = ty;
}
}
}
}
}
printf("%.f\n",ans);
return ;
}
最新文章
- jQuery.fn.extend() 与 jQuery.extend()
- 探 寻 宝 藏--- DP
- 【POJ 2942】Knights of the Round Table(点双连通分量,二分图染色)
- js地理位置获取、显示、轨迹绘制
- [转]C#使用Log4Net记录日志
- LitDB文章
- 学习NAnt Build .CS+Solution+MSBuild+SVN+NUnit+NUnitReport
- Getting NHibernate to generate a HiLo string ID
- Get current time and date on Android
- github上如何合并别人的pull request
- Ubuntu 12.04安装PPTP
- IWorkSpace接口介绍
- JS定义函数的2种方式以及区别简述(为什么推荐第二种方式)
- 虚拟机下Linux系统如何设置IP地址
- Tomcat优化方案
- [转]Android开发环境搭建(图文教程)
- 怎样使用word2013发布csdn博客
- Linux基础操作命令-打包压缩
- HDU 4348 To the moon 主席树 在线更新
- [BZOJ3926][ZJOI2015]诸神眷顾的幻想乡(后缀自动机)