题目链接
题解
啊，模拟退火是个好东西
模拟退火即可
代码
#include<cmath>
#include<cstdio>
#include<algorithm>
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9')c = getchar();
while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();
return x * f;
}
#define INF 1e18
#define eps 1e-10
int n;
struct Node {
double x,y;
} p[101];
double dis(Node a,Node b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double calc(Node a) {
double sum = 0;
for(int i = 1;i <= n;++ i)
sum += dis(a,p[i]);
return sum;
}
#define T 100
#define delta 0.98
double Rand() {
return (double) rand() / (double)RAND_MAX;
}
#define IT 5
double dx[7] = {1,0,-1,0,1};
double solve() {
Node x = p[1];
double res = calc(x);
double t = T;
while(t > eps) {
for(int i = 1;i < IT; ++ i) {
for(int i = 0;i <= 4;++ i) {
Node nx = x;
nx.x += dx[i] * Rand() * t;
nx.y += dx[i + 1] * Rand() * t;
double nxres = calc(nx);
if(nxres < res || Rand() >= exp((nxres - res) / res)) res = nxres,x = nx;
}
}
t *= delta;
}
return res;
}
int main() {
srand(20010901);
n = read();
for(int i = 1;i <= n;++ i)
scanf("%lf%lf",&p[i].x,&p[i].y);
double ans = INF;
for(int i = 1;i <= 10;++ i) {
ans = std:: min(ans,solve());
}
printf("%.0lf
",ans);
}