HDU 3007 Buried memory & ZOJ 1450 Minimal Circle

题意：给出n个点，求最小包围圆。

解法：这两天一直在学这个神奇的随机增量算法……看了这个http://soft.cs.tsinghua.edu.cn/blog/?q=node/1066之后自己写了好久一直写不对……后来在计算几何的模板上找到了…………orz膜拜一下

代码：

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string>

#include<string.h>

#include<math.h>

#include<limits.h>

#include<time.h>

#include<stdlib.h>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define LL long long

using namespace std;

const double eps = 1e-8;

int n;

struct point

{

    double x, y;

}p[505];

bool dy(double x, double y)//x > y

{

    return x > y + eps;

}

double disp2p(point a, point b)//两点距离

{

    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));

}

point l2l_inst_p(point u1, point u2, point v1, point v2)//两直线交点

{

    point ans = u1;

    double t = ((u1.x - v1.x) * (v1.y - v2.y) - (u1.y - v1.y) * (v1.x - v2.x)) /

    ((u1.x - u2.x) * (v1.y - v2.y) - (u1.y - u2.y) * (v1.x - v2.x));

    ans.x += (u2.x - u1.x) * t;

    ans.y += (u2.y - u1.y) * t;

    return ans;

}

point circumcenter(point a, point b, point c)//三角形外接圆

{

    point ua, ub, va, vb;

    ua.x = (a.x + b.x) / 2;

    ua.y = (a.y + b.y) / 2;

    ub.x = ua.x - a.y + b.y;

    ub.y = ua.y + a.x - b.x;

    va.x = (a.x + c.x) / 2;

    va.y = (a.y + c.y) / 2;

    vb.x = va.x - a.y + c.y;

    vb.y = va.y + a.x - c.x;

    return l2l_inst_p(ua, ub, va, vb);

}

void min_cover_circle(point &c, double &r)//最小包围圆

{

    random_shuffle(p, p + n);//貌似是随机排序用的……

    c = p[0];

    r = 0;

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

    if(dy(disp2p(p[i], c), r))

    {

        c = p[i];

        r = 0;

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

        if(dy(disp2p(p[k], c), r))

        {

            c.x = (p[i].x + p[k].x) / 2;

            c.y = (p[i].y + p[k].y) / 2;

            r = disp2p(p[k], c);

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

            if(dy(disp2p(p[j], c), r))

            {

                c = circumcenter(p[i], p[k], p[j]);

                r = disp2p(p[i], c);

            }

        }

    }

}

int main()

{

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

    {

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

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

        point c;

        double r;

        min_cover_circle(c, r);

        printf("%.2lf %.2lf %.2lf\n", c.x, c.y, r);

    }

    return 0;

}