心脏病患者慎入。

模拟退火是一种随机算法，他有一定概率找到最优解，但是也有一定概率找到错解。

然而，他会随着算法的进行不断趋近最优解。

下面听一下这个音乐，看一看模拟退火是不是越退越趋近“低音”。（原题：星星还是树）

（复制下面这段代码然后运行，戴上耳机听，别放太大声）
（运行之后输入：

4
0 0
0 10000
10000 10000
10000 0

）

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <windows.h>
#include <ctime>

#define x first
#define y second

using namespace std;

const int N = 110;
const double MAX = 10000, MIN = 1e-4;
typedef pair<double, double> PDD;

PDD p[N];
int n;
double res = 1e8;

double rand(double l, double r)
{
    return (double)rand() / RAND_MAX * (r - l) + l;
}

double get_dist(PDD a, PDD b)
{
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

double f(PDD a)
{
    double cnt = 0;

    for (int i = 0; i < n; i ++ )
        cnt += get_dist(a, p[i]);

    res = min(cnt, res);
    return cnt;
}

void simulate_anneal()
{
    PDD u(rand(0, MAX), rand(0, MAX));

    for (double t = MAX; t >= MIN; t *= 0.99)
    {
        PDD v(rand(u.x - t, u.x + t), rand(u.y - t, u.y + t));
        double delta = f(v) - f(u);
        if (exp(-delta / t) > rand(0, 1)) u = v, Beep(700, 100); // 当前解优秀，保持解，低音
        else Beep(2022, 100); // 概率接受其他解，高音
    }
}

int main()
{
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ )
        scanf("%lf%lf", &p[i].x, &p[i].y);

    for (int i = 1; i <= 100; i ++ )
        simulate_anneal();

    printf("%.0lf", res);

    return 0;
}