[日常摸鱼]poj2420 A Star not a Tree?
2024-09-04 02:04:42
题意:给定$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过掉惹
最新文章
- 绿色版的Linux.NET——“Jws.Mono”
- 关于RPC
- Myth – 支持变量和数学函数的 CSS 预处理器
- time.h-------日期与时间函数
- Scrapy Learning笔记(四)- Scrapy双向爬取
- php中iconv函数的一个小bug--转载
- IOS网络开发实战(一)
- unbuntu下的root 用户和 sudo 命令
- 201521123031 《Java程序设计》第11周学习总结
- 前后台分离部署时,Niginx上的部署
- Ubuntu LNMP系统搭建Zabbix监控
- zookeeper的原理,5分钟了解zookeeper
- thymeleaf参考手册
- 在Pandas中更改列的数据类型【方法总结】
- Android USER 版本与ENG 版本的差异
- oracle 死锁查询及处理
- 真人测试网站用户体验的超棒在线服务 - Peek by UserTesting
- Ajax同时上传表单序列化参数+自定义参数
- WAF实现扫描器识别
- 设计模式03: Builder 生成器模式(创建型模式)
热门文章
- P4771 八百标兵奔北坡
- C语言精华——内存管理,很多学校学习不到的知识~
- 给集合null,filter结果空集合
- 【mq学习笔记】mq 过期文件删除机制
- C#(三)基础篇—方法,递归,条件分支,循环,三元操作符
- Java动态代理设计模式
- day102:MoFang:后端完成对短信验证码的校验&;基于celery完成异步短信发送&;flask_jwt_extended&;用户登录的API接口
- 在 Windows 中使用 C# 启动其他程序
- 第3.3节 强大的Python列表
- 使用文件描述符作为Python内置函数open的file实参调用示例