Groundhog Build Home - HDU - 3932（模拟退火）

题意

给定一个矩形内的\(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).\n", 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\n", SA());

    }

}