A Star not a Tree? (模拟退火或三分套三套)

题意：

给定个点，要求找到一个点到这个点的欧式距离最小，输出最小距离。

题解：

三分套三分：
当值固定的时候，随着的值从小到大，距离会先减再增，存在一个最小值；同理值固定，值从小到大变化，距离也会先减再增，存在一个最小值。那么就可以考虑用第一个三分求出最小的值，这个三分的check()函数就是当前和最小的值时的距离，而最小的值同样也可以用三分来求，这个三分的check()函数就是当前x和y时的距离

模拟退火：
对于本题，开始随机选一个点（最好是包围盒的中心点）作为出发点，计算评价函数.然后按一定的步长作一次随机位移，到达新点，如果评价函数比更优，一律接受，否则以概率接受，不接受时则仍以为出发点。如此反复位移——接受——位移——接受，位移长度逐次减小，当最终位移长度小于一定的阈值或位移次数达到足够多的次数，算法结束，最后的点作为最优解。

物理学的模拟退火过程中，接受概率、位移的变化速度都与目标函数值有关。实用的模拟退火算法可以简化到与目标函数值无关。对本题来说，接受概率选常值，位移的缩小率选，就能解决问题。经对比试验，也能AC，位移的缩小量设为倒数函数（为初始步长，为迭代序数）都能AC。

三分套三分：

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
pair<double, double> p[maxn];
int n;
double check(double x, double y)
{
    double ans = 0;
    for (int i = 0; i < n; i++)
        ans += sqrt((x - p[i].first) * (x - p[i].first) + (y - p[i].second) * (y - p[i].second));
    return ans;
}
double check(double x)
{
    double l = 0, r = 10000.0;
    double midl, midr;
    for (int i = 0; i < 100; i++)
    {
        midl = l + (r - l) / 2.0;
        midr = midl + (r - midl) / 2.0;
        if (check(x, midl) > check(x, midr))
            l = midl;
        else
            r = midr;
    }
    return check(x, midl);
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%lf%lf", &p[i].first, &p[i].second);
    double l = 0, r = 10000.0;
    double midl, midr;
    for (int i = 0; i < 100; i++)
    {
        midl = l + (r - l) / 2.0;
        midr = midl + (r - midl) / 2.0;
        if (check(midl) > check(midr))
            l = midl;
        else
            r = midr;
    }
    printf("%.0lf\n", check(midl));
    return 0;
}

模拟退火：

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

int n;
double x[100], y[100];
const double PI = acos(-1.0);

double dist(double cx, double cy)
{
    double r = 0.0;
    for (int i = 0; i < n; i++)
        r += sqrt((cx-x[i]) * (cx-x[i]) + (cy-y[i]) * (cy-y[i]));
    return r;
}

int main() {
    double a, b, c, d;
    double tx, ty, step, dx, dy, r, r1;
    scanf("%d", &n);
    a = c = 1e30;
    b = d = 0;
    for (int i = 0; i < n; i++) {    // 包围盒[a,b]*[c,d] 
        scanf("%lf%lf", &x[i], &y[i]);
        a = min(a, x[i]);
        b = max(b, x[i]);
        c = min(c, y[i]);
        d = max(d, y[i]);
    }
    tx = (a + b) / 2;
    ty = (c + d) / 2;
    double s0 = step = max(b-a, d-c);
    r = dist(tx, ty);
    int t = 1;
    srand(100);
    while (t < 1000 && step > 0.01) {
        double theta = (rand() / 32768.0) * PI * 2;
        dx = step * cos(theta);
        dy = step * sin(theta);
        r1 = dist(tx + dx, ty + dy);
        double P = 0.05;
        if (r1 < r || rand() / 32768.0 < P) {
            tx += dx;
            ty += dy;
            r = r1;
        }
    //    step *= 0.95;
        step = s0 / t;
        t++;
    }
    printf("%d\n", (int)(r + 0.5));
    return 0;
}