题目: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 ;
}

最新文章

  1. 常用 meta 整理
  2. Windows Installer 服务启动错误 14007 的解决办法
  3. AutoMapper实现自动CreapMap
  4. .net下灰度模式图像在创建Graphics时出现:无法从带有索引像素格式的图像创建graphics对象 问题的解决方案。
  5. Lua 栈的理解
  6. POJ 1469 COURSES
  7. 7.xmpp版即时聊天
  8. jsp HTTP Status 405 - HTTP method GET is not supported by this URL
  9. ASP图片格式与base64数据互转方法
  10. javascript得知 - js的Date对象函数
  11. 快速构建Windows 8风格应用37-常见发布注意事项
  12. TCMalloc
  13. Charles安装破解及使用
  14. ssh_maven之controller层开发
  15. HQL包含中文查询失败
  16. pyqt5 -——菜单和工具栏
  17. 获取 TUniConnection.SpecificOptions默认值和下拉框列表值
  18. eclipse+pydev 怎么导入已有的python项目
  19. Catch That Cow--POJ3278
  20. ASP.NET Core 2 学习笔记(七)路由

热门文章

  1. 安装惠普M1136打印机一直处于“新设备已连接”状态怎么办?
  2. 百科知识 ass文件如何打开
  3. Oracle Apex 有用笔记系列 6 - 可编辑交互报告 Editable Interactive Report
  4. pascals-triangleI、II——生成规律的三角形
  5. 【java读书笔记】——Collection集合之六大接口(Collection、Set、List、Map、Iterator和Comparable)
  6. JavaScript 内存机制
  7. 第14章8节《MonkeyRunner源代码剖析》 HierarchyViewer实现原理-获取控件列表并建立控件树
  8. windows常用命令(转载)
  9. spring源码解析——2容器的基本实现(第2版笔记)
  10. CSS的两种盒模型