poj1379

poj1379

题意

给出 n 个洞的坐标，要求找到一点使得这一点距离最近洞的距离最远。

分析

通过这道题学习一下模拟退火算法，

这种随机化的算法，在求解距离且精度要求较小时很有用。

简而言之，由随机选取的多个初始点，进行多次的随机变换，并根据是否更优而选择是否保留答案，

那么首先要选择两个值，delta 表示初始最大变换的半径（即对应初始的火温），d 控制半径缩小的快慢（火温减小的快慢）。

这道题，比较直白，随机变换就是改变坐标的位置（通过半径和角度就可以变换坐标，当然角度也是随机的），若变换后距所有点的距离增大了那么则更优。

code

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<ctime>

using namespace std;

const int MAXN = 1005;

const int MAXP = 20; // 随机选取 20 个点

const double PI = acos(-1.0);

double X, Y;

int n;

double dis[100];

struct P

{

    double x, y;

    P() {}

    P(double _x, double _y) : x(_x), y(_y) {}

    P operator - (P p)

    {

        return P(x - p.x, y - p.y);

    }

    double dis()

    {

        return sqrt(x * x + y * y);

    }

}a[MAXN], ans[MAXN];

double getMinDis(P p)

{

    double as = 1e9;

    for(int i = 0; i < n; i++)

    {

        as = min(as, (p - a[i]).dis());

    }

    return as;

}

P SA()

{

    for(int i = 0; i < MAXP; i++)

    {

        ans[i].x = (rand() % 1000 + 1) / 1000.0 * X;

        ans[i].y = (rand() % 1000 + 1) / 1000.0 * Y;

        dis[i] = getMinDis(ans[i]);

    }

    double delta = max(X, Y) / sqrt(n * 1.0), d = 0.9;

    while(delta > 0.01) // 边界最小值

    {

        for(int i = 0; i < MAXP; i++)

        {

            for(int j = 0; j < 20; j++)

            {

                P t = ans[i];

                double angle = rand() % 1000 / 1000.0 * 2 * PI;

                t.x += delta * cos(angle) * (rand() % 1000 / 1000.0);

                t.y += delta * sin(angle) * (rand() % 1000 / 1000.0);

                if(t.x < 0 || t.x > X || t.y < 0 || t.y > Y)  continue;

                double tmp = getMinDis(t);

                if(tmp > dis[i])

                {

                    dis[i] = tmp;

                    ans[i] = t;

                }

            }

        }

        delta *= d;

    }

    double dd = 0;

    int pp = 0;

    for(int i = 0; i < MAXP; i++)

    {

        if(dis[i] > dd)

        {

            dd = dis[i];

            pp = i;

        }

    }

    return ans[pp];

}

int main()

{

    srand(time(0));

    int T;

    for(scanf("%d", &T); T--;)

    {

        scanf("%lf%lf%d", &X, &Y, &n);

        for(int i = 0; i < n; i++)

        {

            scanf("%lf%lf", &a[i].x, &a[i].y);

        }

        P p = SA();

        printf("The safest point is (%.1f, %.1f).\n", p.x, p.y);

    }

    return 0;

}