hdu 3007【最小圆覆盖-随机增量法模板】

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=505;
int n;
double r;
struct dian
{
	double x,y;
	dian(double X=0,double Y=0)
	{
		x=X,y=Y;
	}
	dian operator + (const dian &a) const
	{
		return dian(x+a.x,y+a.y);
	}
	dian operator - (const dian &a) const
	{
		return dian(x-a.x,y-a.y);
	}
	dian operator * (const double &a) const
	{
		return dian(x*a,y*a);
	}
	dian operator / (const double &a) const
	{
		return dian(x/a,y/a);
	}
}p[N],c;
double dis(dian a,dian b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double cj(dian a,dian b)
{
	return a.x*b.y-a.y*b.x;
}
dian yx(dian a,dian b,dian c)
{
	dian p=b-a,q=c-a;
	double c1=(p.x*p.x+p.y*p.y)/2,c2=(q.x*q.x+q.y*q.y)/2,d=cj(p,q);
	return a+dian(c1*q.y-c2*p.y,c2*p.x-c1*q.x)/d;
}
int main()
{
	while(scanf("%d",&n)&&n)
	{
		for(int i=1;i<=n;i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		random_shuffle(p+1,p+1+n);
		c=p[1],r=0;
		for(int i=2;i<=n;i++)
			if(dis(p[i],c)-r>0)
			{
				c=p[i],r=0;
				for(int j=1;j<i;j++)
					if(dis(p[j],c)-r>0)
					{
						c=(p[i]+p[j])/2,r=dis(p[j],c);
						for(int k=1;k<j;k++)
							if(dis(p[k],c)-r>0)
								c=yx(p[i],p[j],p[k]),r=dis(p[k],c);
					}
			}
		printf("%.2f %.2f %.2f
",c.x,c.y,r);
	}
	return 0;
}
原文地址:https://www.cnblogs.com/lokiii/p/8503201.html