poj 2420 A Star not a Tree? —— 模拟退火
2024-08-30 09:08:02
题目:http://poj.org/problem?id=2420
给出 n 个点的坐标,求费马点;
上模拟退火。
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<cmath>
#define eps 1e-17
#define dt 0.99
using namespace std;
typedef double db;
int const xn=;
int n,xx[xn],yy[xn];
db ansx,ansy,ans;
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();
return f?ret:-ret;
}
db dist(db x,db y,db a,db b){return sqrt((x-a)*(x-a)+(y-b)*(y-b));}
db cal(db x,db y)
{
db ret=;
for(int i=;i<=n;i++)ret+=dist(x,y,xx[i],yy[i]);
return ret;
}
void SA()
{
db T=,x=ansx,y=ansy,lst=ans,tx,ty,tmp;
while(T>eps)
{
tx=x+(rand()*-RAND_MAX)*T;
ty=y+(rand()*-RAND_MAX)*T;
tmp=cal(tx,ty); db delt=tmp-lst;
if(delt<||exp(delt/T)*RAND_MAX<rand())x=tx,y=ty,lst=tmp;
if(tmp<ans)ansx=tx,ansy=ty,ans=tmp;
T*=dt;
}
}
int main()
{
n=rd(); int sx=,sy=;
for(int i=;i<=n;i++)xx[i]=rd(),yy[i]=rd(),sx+=xx[i],sy+=yy[i];
ansx=1.0*sx/n; ansy=1.0*sy/n; ans=cal(ansx,ansy);
SA(); SA(); SA();
printf("%.0lf\n",ans);
return ;
}
最新文章
- 常用 meta 整理
- Windows Installer 服务启动错误 14007 的解决办法
- AutoMapper实现自动CreapMap
- .net下灰度模式图像在创建Graphics时出现:无法从带有索引像素格式的图像创建graphics对象 问题的解决方案。
- Lua 栈的理解
- POJ 1469 COURSES
- 7.xmpp版即时聊天
- jsp HTTP Status 405 - HTTP method GET is not supported by this URL
- ASP图片格式与base64数据互转方法
- javascript得知 - js的Date对象函数
- 快速构建Windows 8风格应用37-常见发布注意事项
- TCMalloc
- Charles安装破解及使用
- ssh_maven之controller层开发
- HQL包含中文查询失败
- pyqt5 -——菜单和工具栏
- 获取 TUniConnection.SpecificOptions默认值和下拉框列表值
- eclipse+pydev 怎么导入已有的python项目
- Catch That Cow--POJ3278
- ASP.NET Core 2 学习笔记(七)路由
热门文章
- 安装惠普M1136打印机一直处于“新设备已连接”状态怎么办?
- 百科知识 ass文件如何打开
- Oracle Apex 有用笔记系列 6 - 可编辑交互报告 Editable Interactive Report
- pascals-triangleI、II——生成规律的三角形
- 【java读书笔记】——Collection集合之六大接口(Collection、Set、List、Map、Iterator和Comparable)
- JavaScript 内存机制
- 第14章8节《MonkeyRunner源代码剖析》 HierarchyViewer实现原理-获取控件列表并建立控件树
- windows常用命令(转载)
- spring源码解析——2容器的基本实现(第2版笔记)
- CSS的两种盒模型