Groundhog Build Home

题意

给定一个矩形内的(n)个点，在矩形中找一个点，离其他点的最大距离最小。

题解

模拟退火。

这个题需要(x)和(y)坐标随机动的时候多随机几次。否则就WA了。另外由于随机多次，如果温度变化率太小，就会TLE。

代码

//#include <bits/stdc++.h>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <iostream>

#define FOPI freopen("in.txt", "r", stdin)
#define FOPO freopen("out.txt", "w", stdout)

using namespace std;
typedef long long LL;
const int maxn = 1000 + 5;
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
const double start_T = 20000;

struct Point
{
    double x, y, z;
    Point() {}
    Point(double _x, double _y, double _z = 0):x(_x), y(_y), z(_z) {}
}a[maxn];

int dx[] = {1, 1, 1, -1, -1, -1, 0, 0},
    dy[] = {0, 1, -1, 0, 1, -1, -1, 1};

int n;
int X, Y;

double dist(Point a, Point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) + 1e-10);
}

double getMax(Point p)
{
    double res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res, dist(a[i], p));
    return res;
}

double SA()
{
    Point p(rand()%X, rand()%Y), to;
    double T = start_T, rate = 0.94;
    double fx, fy, ans = getMax(p);

    while(T > eps)
    {
        double tmp = inf;
        for (int times = 1; times <= 20; times++)
        for (int i = 0; i < 8; i++)
        {
            fx = p.x + dx[i] / start_T * T * (rand()%X);
            fy = p.y + dy[i] / start_T * T * (rand()%Y);

            if (fx < 0) fx = 0;
            if (fy < 0) fy = 0;
            if (fx > X) fx = X;
            if (fy > Y) fy = Y;

            double d = getMax(Point(fx, fy));
            if (d < tmp)
            {
                tmp = d;
                to = Point(fx, fy);
            }
        }

        T *= rate;
        if (tmp < eps) continue;

        if (tmp < ans || (rand()%1000)/1000.0 < exp(-fabs(ans-tmp)/T*start_T))
        {
            ans = tmp;
            p = to;
        }
    }
    printf("(%.1f,%.1f).
", p.x, p.y);
    return ans;
}

int t;
int main()
{
//    FOPI;
    srand(time(NULL));
    while(~scanf("%d%d%d", &X, &Y, &n))
    {
        for (int i = 1; i <= n; i++)
            scanf("%lf%lf", &a[i].x, &a[i].y);
        printf("%.1f
", SA());
    }
}