题意：给出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
", c.x, c.y, r);
}
return 0;
}