求一个半径最小的圆覆盖住所有点

使用随机增量的方法，每次找到一个不在当前圆内的点，将圆调整扩大至该点在圆周上，期望复杂度O(n)。注意在调用getMinCover之前应先把point[]中的点打乱顺序。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
const int MAXN = 505;
const double EPS = 1e-6;
double PI;
struct Point
{
    Point() {}
    Point(double _x, double _y): x(_x), y(_y) {}
    double getDis(Point rhs)
    {
        double xx = rhs.x - x, yy = rhs.y - y;
        return sqrt(xx * xx + yy * yy);
    }

    void input(){scanf("%lf%lf", &x, &y);}
    double x, y;
};
double operator ^(Point lhs, Point rhs){return lhs.x * rhs.y - lhs.y * rhs.x;}
Point operator +(Point lhs, Point rhs){return Point(lhs.x + rhs.x, lhs.y + rhs.y);}
Point operator -(Point lhs, Point rhs){return Point(lhs.x - rhs.x, lhs.y - rhs.y);}
Point operator /(Point lhs, double rhs){return Point(lhs.x / rhs, lhs.y / rhs);}
Point operator *(Point lhs, double rhs){return Point(lhs.x * rhs, lhs.y * rhs);}

Point point[MAXN];
int n;
Point center;
double radius;

bool isPointInCircle(Point &t)
{
    return t.getDis(center) <= radius + EPS;
}

void adjustCircleCenter(Point &p0, Point &p1, Point &p2)
{
    double a1 = p1.x - p0.x, b1 = p1.y - p0.y, c1 = (a1 * a1 + b1 * b1) / 2.0;
    double a2 = p2.x - p0.x, b2 = p2.y - p0.y, c2 = (a2 * a2 + b2 * b2) / 2.0;
    double d = a1 * b2 - a2 * b1;
    center.x = p0.x + (c1 * b2 - c2 * b1) / d;
    center.y = p0.y + (a1 * c2 - a2 * c1) / d;
}

void getMinCircleCover()
{
    radius = 0.0;
    center = point[0];
    for(int i = 1; i < n; ++i)
    {
        if(!isPointInCircle(point[i]))
        {
            center = point[i];
            radius = 0;
            for(int j = 0; j < i; ++j)
            {
                if(!isPointInCircle(point[j]))
                {
                    center = (point[i] + point[j]) / 2.0;
                    radius = center.getDis(point[j]);
                    for(int k = 0; k < j; ++k)
                    {
                        if(!isPointInCircle(point[k]))
                        {
                            adjustCircleCenter(point[i], point[j], point[k]);
                            radius = center.getDis(point[k]);
                        }
                    }
                }
            }
        }
    }
}

int main()
{
    while(scanf("%d", &n) && n != 0)
    {
        for(int i = 0; i < n; ++i) point[i].input();
        getMinCircleCover();
        printf("%.2lf %.2lf %.2lf\n", center.x, center.y, radius);
    }
}