poj2069

poj2069

题意

求一个覆盖所有点的最小球体的半径。即求空间内一点到所有点的距离的最大值最小的点。

分析

模拟退火算法，但这道题竟然不用随机函数就能过了，主要体现了算法的渐近收敛性，

起始点随意取，然后找到相距最远的点，按比例向这个点位移，而这个比例在一定程度上是逐渐减小的，最终达到要求的精度。

即使位移后得到的点距其他点的距离增大了还是要移动到那个点，否则会错。

code

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

const int MAXN = 33;

typedef pair<double, int> Pair;

int n;

struct P

{

    double x, y, z;

    P() {}

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

    P operator - (P p)

    {

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

    }

    double dis()

    {

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

    }

} a[MAXN];

Pair getMaxDis(P p)

{

    double dd = 0;

    int ii = 0;

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

    {

        double tmpd;

        if((tmpd = (a[i] - p).dis()) > dd)

        {

            dd = tmpd;

            ii = i;

        }

    }

    return Pair(dd, ii);

}

double SA()

{

    P t;

    t.x = 0;

    t.y = 0;

    t.z = 0;

    double delta = 100, d = 0.98;

    Pair dis = getMaxDis(t);

    double maxd = dis.first;

    int id = dis.second;

    while(delta > 1e-7)

    {

        for(int j = 0; j < 1; j++) // 这样就能过了...

        {

            double rate = delta / maxd;

            t.x += (a[id].x - t.x) * rate;

            t.y += (a[id].y - t.y) * rate;

            t.z += (a[id].z - t.z) * rate;

            dis = getMaxDis(t);

            id = dis.second;

            maxd = dis.first;

        }

        delta *= d;

    }

    return maxd;

}

int main()

{

    while(~scanf("%d", &n) && n)

    {

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

        {

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

        }

        printf("%.5f\n", SA());

    }

    return 0;

}