题目:http://poj.org/problem?id=2420

精度设成1e-17,做三遍。ans设成double,最后再取整。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<ctime>
#define db double
using namespace std;
const int N=;
const db dc=0.99,eps=1e-;
int n,nx[N],ny[N];
db px,py,ans;
db dis(db x0,db y0,db x1,db y1)
{
return sqrt((x0-x1)*(x0-x1)+(y0-y1)*(y0-y1));
}
db calc(db x,db y)
{
db ret=;
for(int i=;i<=n;i++)ret+=dis(nx[i],ny[i],x,y);
return ret;
}
db gtrd(db T){return (rand()*-RAND_MAX)*T;}
void SA(db T)
{
db x0=px,y0=py,pr=calc(x0,y0),x,y,cr;
while(T>eps)
{
x=x0+gtrd(T); y=y0+gtrd(T); cr=calc(x,y);
if(cr<pr||(exp((cr-pr)/T)*RAND_MAX<rand()))
{
ans=min(ans,cr);
x0=x;y0=y;pr=cr;
}
T*=dc;
}
}
int main()
{
srand(time());
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d%d",&nx[i],&ny[i]),px+=nx[i],py+=ny[i];
px/=n; py/=n; ans=calc(px,py);
SA();SA();SA();
printf("%.0lf\n",ans);
return ;
}

最新文章

  1. 在桌面程序上和Metro/Modern/Windows store app的交互(相互打开,配置读取)
  2. Android中常用控件及属性
  3. 强大的&lt;canvas&gt;
  4. DOM的相关优化
  5. cURL POST command line on WINDOWS RESTful service
  6. Jquery easyui Tree的简单使用
  7. contentOffset,frame,bounds,contentSize,ContentInset
  8. c 函数及指针学习 10
  9. ppshu
  10. 关于Eclipse中的开源框架EMF(Eclipse Modeling Framework)
  11. linux定时运行命令脚本——crontab
  12. Hibernate简单的基础理论
  13. 201521123016 《Java程序设计》第9周学习总结
  14. 深入学习JS执行--单线程的JS
  15. R语言学习 第九篇:plyr包
  16. c++/qt的数据序列化和反序列化
  17. 聚宽投资研究获取A股05年至今全部数据
  18. netty中的传输
  19. python学习路线--从入门到入土
  20. Node.js中文乱码解决方法

热门文章

  1. firework压缩图片类似于GD库中压缩图片的思路
  2. python升级或者其他原因把yum搞坏了
  3. 【Python基础】之异常
  4. 你的JVM还好吗?GC初步诊断
  5. Oracle -- 连接每行的内容
  6. 模式识别之svm()---支持向量机svm 简介1995
  7. &lt;转载&gt; pycharm快捷键及一些常用设置
  8. 【BZOJ3745】[Coci2015]Norma cdq分治
  9. JavaScript中实现继承
  10. 按模板导出Excel