# 最小圆覆盖 学习笔记【计算几何】

## 代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define db double
#define eps 1e-12
struct pnt
{
db x,y;
pnt(db x,db y)
{
this->x=x;
this->y=y;
}
pnt(){}
friend pnt operator +(pnt a,pnt b)
{return pnt(a.x+b.x,a.y+b.y);}
friend pnt operator -(pnt a,pnt b)
{return pnt(a.x-b.x,a.y-b.y);}
friend db operator *(pnt a,pnt b)
{return a.x*b.y-a.y*b.x;}
db dis()
{return sqrt(x*x+y*y);}
pnt times(db k)
{return pnt(k*x,k*y);}
}p[100100];
pnt its(pnt a,pnt b,pnt c,pnt d)//ab和cd交点
{
db u=(c-a)*(d-a);
db D=u+(d-b)*(c-b);
return a+(b-a).times(u/D);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%lf%lf",&p[i].x,&p[i].y);
std::random_shuffle(p+1,p+1+n);
pnt c(0,0);
db r=0.0;
for(int i=1;i<=n;++i)
{
if((p[i]-c).dis()<r+eps)
continue;
c=p[i];
r=0.0;
for(int j=1;j<i;++j)
{
if((p[j]-c).dis()<r+eps)
continue;
r=(p[j]-p[i]).dis()/2;
c=p[i]+(p[j]-p[i]).times(.5);
for(int k=1;k<j;++k)
{
if((p[k]-c).dis()<r+eps)
continue;
pnt a=p[j]-p[i];
pnt f=p[i]+a.times(.5);
pnt b=p[k]-p[j];
pnt g=p[j]+b.times(.5);
c=its(f,f+pnt(-a.y,a.x),g,g+pnt(-b.y,b.x));
r=(c-p[i]).dis();
}
}
}
printf("%.10lf\n%.10lf %.10lf\n",r,c.x,c.y);
return 0;
}

### 3 说点什么

0 Followers

Most reacted comment
0 Comment authors
Recent comment authors
Subscribe

[…] Find More on to that Topic: wjyyy.top/3347.html […]