The Moving Points - HDU - 4717 （模拟退火）

题意

二维空间中有\(n\)个运动的点，每个点有一个初始坐标和速度向量。求出一个时间\(T\)，使得此时任意两点之间的最大距离最小。输出\(T\)和最大距离。

题解

模拟退火。

这个题告诉了我，初始步长要够大。这是很重要的。

//#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 = 300 + 5;

const double eps = 1e-6;

const int inf = 0x3f3f3f3f;

const double start_T = 2000;

struct Point

{

    double x, y, z;

    Point() {}

    Point(double _x, double _y, double _z = 0):x(_x), y(_y), z(_z) {}

}a[maxn];

double vx[maxn], vy[maxn];

int n;

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);

}

Point pos[maxn];

double getMax(double ti)

{

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

        pos[i] = Point(a[i].x + vx[i]*ti, a[i].y + vy[i]*ti);

    double res = 0;

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

        for (int j = i+1; j <= n; j++)

        res = max(res, dist(pos[i], pos[j]));

    return res;

}

double SA()

{

    double T = start_T, rate = 0.92;

    double ti = 0, ans = getMax(ti), to;

    while(T > eps)

    {

        double tmp = inf;

        for (int i = 1; i <= 5; i++)

        {

            double nextt = ti + T / start_T * (rand() % inf);

            double lastt = ti - T / start_T * (rand() % inf);

            double d1 = getMax(nextt), d2 = getMax(lastt);

            if (d1 < tmp) tmp = d1, to = nextt;

            if (d2 < tmp && lastt > eps) tmp = d2, to = lastt;

        }

        if (tmp < ans || (rand()%1000)/1000.0 < exp(-fabs(ans-tmp)/T*start_T))

        {

            ans = tmp;

            ti = to;

        }

        T *= rate;

    }

    printf("%.2f %.2f\n", ti, ans);

    return ans;

}

int t;

int main()

{

//    FOPI;

    srand(time(NULL));

    scanf("%d", &t);

    for (int ca = 1; ca <= t; ca++)

    {

        scanf("%d", &n);

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

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

        printf("Case #%d: ", ca);

        SA();

    }

}