题意:给定$n$个点,找一个点使得这个点到所有点的距离之和最小,求出这个最小距离


传说中的模拟退火…

#include<cstdio>
#include<ctime>
#include<cmath>
#include<cstdlib>
const int N=105;
struct point
{
double x,y;
}ps[N];
int n;
double t,ans,tans,tx,ty,nx,ny,temp; inline double get(int x){return 1.0*((rand()%x)*(rand()%x)%x);}
inline double sqr(double x){return x*x;}
inline double dis(double x,double y,point &p)
{
return sqrt(sqr(x-p.x)+sqr(y-p.y));
}
inline double calc(double x,double y)
{
double res=0;
for(register int i=1;i<=n;i++)res+=dis(x,y,ps[i]);
return res;
}
int main()
{
scanf("%d",&n);nx=ny=0;t=100000;
for(register int i=1;i<=n;i++)
{
scanf("%lf%lf",&ps[i].x,&ps[i].y);
nx+=ps[i].x;ny+=ps[i].y;
}
nx/=n;ny/=n;tans=ans=calc(nx,ny);
while(t>0.02)
{
tx=ty=0;
for(register int i=1;i<=n;i++)
{
tx+=(ps[i].x-nx)/dis(nx,ny,ps[i]);
ty+=(ps[i].y-ny)/dis(nx,ny,ps[i]);
}
temp=calc(nx+tx*t,ny+ty*t);
if(temp<ans)
{
tans=ans=temp;nx+=tx*t;ny+=ty*t;
}else if(log((temp-ans)/t)<get(10000)/10000.0)
{
ans=temp;nx+=tx*t;ny+=ty*t;
}
t*=0.9;
}
if(tans<ans)ans=tans;
printf("%.0lf",ans);
return 0;
}

_(:з」∠)_瞎调参数0ms过掉惹

最新文章

  1. 绿色版的Linux.NET——“Jws.Mono”
  2. 关于RPC
  3. Myth – 支持变量和数学函数的 CSS 预处理器
  4. time.h-------日期与时间函数
  5. Scrapy Learning笔记(四)- Scrapy双向爬取
  6. php中iconv函数的一个小bug--转载
  7. IOS网络开发实战(一)
  8. unbuntu下的root 用户和 sudo 命令
  9. 201521123031 《Java程序设计》第11周学习总结
  10. 前后台分离部署时,Niginx上的部署
  11. Ubuntu LNMP系统搭建Zabbix监控
  12. zookeeper的原理,5分钟了解zookeeper
  13. thymeleaf参考手册
  14. 在Pandas中更改列的数据类型【方法总结】
  15. Android USER 版本与ENG 版本的差异
  16. oracle 死锁查询及处理
  17. 真人测试网站用户体验的超棒在线服务 - Peek by UserTesting
  18. Ajax同时上传表单序列化参数+自定义参数
  19. WAF实现扫描器识别
  20. 设计模式03: Builder 生成器模式(创建型模式)

热门文章

  1. P4771 八百标兵奔北坡
  2. C语言精华——内存管理,很多学校学习不到的知识~
  3. 给集合null,filter结果空集合
  4. 【mq学习笔记】mq 过期文件删除机制
  5. C#(三)基础篇—方法,递归,条件分支,循环,三元操作符
  6. Java动态代理设计模式
  7. day102:MoFang:后端完成对短信验证码的校验&amp;基于celery完成异步短信发送&amp;flask_jwt_extended&amp;用户登录的API接口
  8. 在 Windows 中使用 C# 启动其他程序
  9. 第3.3节 强大的Python列表
  10. 使用文件描述符作为Python内置函数open的file实参调用示例