poj2420(模拟退火大法好)
2024-10-21 03:57:15
//
// main.cpp
// poj2420
//
// Created by 陈加寿 on 16/2/13.
// Copyright © 2016年 chenhuan001. All rights reserved.
// #include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std; struct Point
{
int x,y;
}g[110];
#define eps 1e-6 double myrand()
{
long long a=rand();
long long b=rand();
a = a*b%200000-100000;
return ((double)a/10);
} double fuc(double x,double y,int n)
{
double sum=0;
for(int i=0;i<n;i++)
sum += sqrt( (x-g[i].x)*(x-g[i].x)+(y-g[i].y)*(y-g[i].y) );//不是哈密顿距离
return sum;
} double cold(int n)
{
double tx=0,ty=0;
double K=1;
double min=fuc(tx,ty,n);
while(K>eps)
{
double xx,yy;
xx=myrand()*K+tx;
yy=myrand()*K+ty;
double tmp=fuc(xx,yy,n);
if( tmp < min )
{
min=tmp;
tx=xx;
ty=yy;
}
K*=0.98;
}
return min;
} int main(int argc, const char * argv[]) {
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d%d",&g[i].x,&g[i].y);
}
double ans = 1e9;
ans = min(ans,cold(n));
printf("%.0lf\n",ans);
return 0;
}
最新文章
- 了解HTML表单之input元素的30个元素属性
- NOIP2007矩阵取数[DP|高精度]
- Android手机浏览器访问本地网络相关问题
- Quartz.net开源作业调度框架使用详解(转)
- 如何通过Button获取UITableViewCell
- 小白日记48:kali渗透测试之Web渗透-XSS(二)-漏洞利用-键盘记录器,xsser
- Redis 列表(List)
- 一道google面试题(dp)
- 图数据库之Pregel
- Json.Net6.0
- SpringMVC第一天(其他)
- perl 正则表达式之漫游
- 分布式任务调度——quartz + spring + 数据库
- 详细集成Redis (一)
- 安装zip版mysql
- 第三部分:Android 应用程序接口指南---第二节:UI---第四章 Action Bar
- Python3学习之路~5.8 shelve模块
- [工作日志] 2018-11-21 主要: 改bug 自测 :校验图片后缀名
- cxGrid之checkbox小结
- Java 中 Map与JavaBean实体类之间的相互转化