用随机增量法。讲解：https://blog.csdn.net/jokerwyt/article/details/79221345
设点集A的最小覆盖圆为g(A)
可以发现:
1.g(A)是唯一的
2.g(A)可以由<=3个点唯一确定
①由一个点确定（所有点重合时）
②由两个点确定（圆直径必定为两点连线）
③由三个点确定（圆必定是过三点的唯一圆）
把A中在g(A)上的点叫做关键点
可以发现：若点b不在g(A)内（b不属于A），则b是g(A+b)的关键点
证明：如果b不是g(A+b)的关键点，即b在g(A+b)内，那么显然g(A+b)=g(A)，b在g(A)内，与题意矛盾
记点l,点l+1,点l+2,..,点r构成的集合为l..r
现在题目就是要求g(1..i)
设g(A,B)表示点集A的最小覆盖圆，并且点集B中所有点都在这个圆上
设Cir(x,y)表示一个圆心在点x，半径为y的圆
设Cir(a,b,c)表示由a,b,c三点确定的圆
g(1..i)
=g(1..i-1)(如果i属于g(1..i-1))
=g(1..i-1,i)(如果i不属于g(1..i-1))
g(空集,i)=Cir(i,0)
g(1..p,i)
=g(1..p-1,i)(如果p属于g(1..p-1,i))
=g(1..p-1,{i,p})(如果p不属于g(1..p-1,i))
g(空集,{i,j})=Cir((i,j中点),dis(i,j)/2)
g(1..q,{i,p})
=g(1..q-1,{i,p})(如果q属于g(1..q,{i,p}))
=g(1..q-1,{i,p,q})(如果q不属于g(1..q,{i,p}))
g(任意集合,{i,j,k})=Cir(i,j,k)
可以把以上过程改写成循环(以上相当于给出了从g(1..i-1)转移到g(1..i)的方法)
（以下代码交洛谷）
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<ctime>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
namespace X
{
const double eps=1e-;
struct Point
{
double x,y;
Point(double x=,double y=):x(x),y(y){}
};
typedef Point Vec;
Vec operator+(const Vec& a,const Vec& b)
{
return Vec(a.x+b.x,a.y+b.y);
}
Vec operator-(const Vec& a,const Vec& b)
{
return Vec(a.x-b.x,a.y-b.y);
}
Vec operator*(double a,const Vec& b)
{
return Vec(a*b.x,a*b.y);
}
Vec operator*(const Vec& a,double b)
{
return Vec(b*a.x,b*a.y);
}
Vec operator/(const Vec& a,double b)
{
return Vec(a.x/b,a.y/b);
}
int dcmp(double x)
//正为1，负为-1，0为0
{
if(fabs(x)<eps) return ;
return x<?-:;
}
bool operator==(const Vec& a,const Vec& b)
//判向量相等
{
return dcmp(a.x-b.x)==&&dcmp(a.y-b.y)==;
}
double dot(const Vec& a,const Vec& b)
//点积
{
return a.x*b.x+a.y*b.y;
}
double cross(const Vec& a,const Vec& b)
//叉积
{
return a.x*b.y-a.y*b.x;
}
double len(const Vec& x)
//向量长度
{
return sqrt(dot(x,x));
}
double angle(const Vec& a,const Vec& b)
//夹角，0~180°
{
return acos(dot(a,b)/len(a)/len(b));
}
double angle1(const Vec& a,const Vec& b)
//夹角，带方向，a到b逆时针为正，顺时针为负，共线为0
{
return acos(dot(a,b)/len(a)/len(b))*(dcmp(cross(a,b)));
}
Vec rotate(const Vec& a,double rad)
//旋转，正为逆时针，负为顺时针
{
return Vec(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}
Vec normal(const Vec& x)
//单位法线，左转90°后除以自身长度
{
double l=len(x);
return Vec(-x.y/l,x.x/l);
}
Vec normal1(const Vec& x)
//法线，不归一化
{
return Vec(-x.y,x.x);
}
Point lineline(const Point& p,const Vec& v,const Point& q,const Vec& w)
//直线交点,GetLineIntersection
{
return p+v*cross(w,p-q)/cross(v,w);
}
double ptline(const Point& p,const Point& a,const Point& b)
//point_to_line,点到直线距离,DistanceToLine
{
Vec v1=b-a,v2=p-a;
return fabs(cross(v1,v2)/len(v1));
}
double ptseg(const Point& p,const Point& a,const Point& b)
//point_to_segment,点到线段距离,DistanceToSegment
{
if(a==b) return len(p-a);
//Vec v1=b-a,v2=a-p,v3=p-b;
Vec v1=b-a,v2=p-a,v3=p-b;
if(dcmp(dot(v1,v2))<) return len(v2);
else if(dcmp(dot(v1,v3))>) return len(v3);
else return fabs(cross(v1,v2)/len(v1));
}
double area2(const Point& a,const Point& b,const Point& c)
//叉积对应平行四边形的面积
{
return cross(b-a,c-a);
}
double thrarea(const Point& a,const Point& b,const Point& c)
//三角形面积，绝对值
{
return fabs(cross(b-a,c-a)/);
}
bool ifpar(const Vec& a,const Vec& b)
//ifParallel
//是否共线/平行
{
return dcmp(cross(a,b))==;
}
Point pointline(const Point& p,const Point& a,const Vec& v)
//点在直线上投影,GetLineProjection
{
return a+v*(dot(p-a,v)/dot(v,v));
}
double sqr(double x){return x*x;}
double dis(const Point &x,const Point &y)
{
return sqrt(sqr(x.x-y.x)+sqr(x.y-y.y));
}
};
using namespace X;
Point p[];
int n;
Point a;
double r;
void make(const Point &x,const Point &y)
{
Vec t=(y-x)/;
a=x+t;
r=len(t);
}
void make(const Point &x,const Point &y,const Point &z)
{
Vec t1=(y-x)/,t2=(z-y)/;
Point x1=x+t1,y1=y+t2;
t1=normal1(t1);t2=normal1(t2);
a=lineline(x1,t1,y1,t2);
r=dis(a,x);
}
bool ok(const Point &x)
{
return dis(x,a)<=r;
}
int main()
{
int i,j,k;
srand(time());
scanf("%d",&n);
for(i=;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
random_shuffle(p+,p+n+);
a=p[];r=;
for(i=;i<=n;i++)
if(!ok(p[i]))
{
a=p[i];r=;
for(j=;j<i;j++)
if(!ok(p[j]))
{
make(p[i],p[j]);
for(k=;k<j;k++)
if(!ok(p[k]))
{
make(p[i],p[j],p[k]);
}
}
}
printf("%.10f\n",r);
printf("%.10f %.10f\n",a.x,a.y);
return ;
}
此题同上面题，改一下输出格式就一样
bzoj数据稍微有点卡精度，把存储半径改成存储半径的平方就可以A了
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<ctime>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
namespace X
{
const double eps=1e-;
struct Point
{
double x,y;
Point(double x=,double y=):x(x),y(y){}
};
typedef Point Vec;
Vec operator+(const Vec& a,const Vec& b)
{
return Vec(a.x+b.x,a.y+b.y);
}
Vec operator-(const Vec& a,const Vec& b)
{
return Vec(a.x-b.x,a.y-b.y);
}
Vec operator*(double a,const Vec& b)
{
return Vec(a*b.x,a*b.y);
}
Vec operator*(const Vec& a,double b)
{
return Vec(b*a.x,b*a.y);
}
Vec operator/(const Vec& a,double b)
{
return Vec(a.x/b,a.y/b);
}
int dcmp(double x)
//正为1，负为-1，0为0
{
if(fabs(x)<eps) return ;
return x<?-:;
}
bool operator==(const Vec& a,const Vec& b)
//判向量相等
{
return dcmp(a.x-b.x)==&&dcmp(a.y-b.y)==;
}
double dot(const Vec& a,const Vec& b)
//点积
{
return a.x*b.x+a.y*b.y;
}
double cross(const Vec& a,const Vec& b)
//叉积
{
return a.x*b.y-a.y*b.x;
}
double len(const Vec& x)
//向量长度
{
return sqrt(dot(x,x));
}
double angle(const Vec& a,const Vec& b)
//夹角，0~180°
{
return acos(dot(a,b)/len(a)/len(b));
}
double angle1(const Vec& a,const Vec& b)
//夹角，带方向，a到b逆时针为正，顺时针为负，共线为0
{
return acos(dot(a,b)/len(a)/len(b))*(dcmp(cross(a,b)));
}
Vec rotate(const Vec& a,double rad)
//旋转，正为逆时针，负为顺时针
{
return Vec(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}
Vec normal(const Vec& x)
//单位法线，左转90°后除以自身长度
{
double l=len(x);
return Vec(-x.y/l,x.x/l);
}
Vec normal1(const Vec& x)
//法线，不归一化
{
return Vec(-x.y,x.x);
}
Point lineline(const Point& p,const Vec& v,const Point& q,const Vec& w)
//直线交点,GetLineIntersection
{
return p+v*cross(w,p-q)/cross(v,w);
}
double ptline(const Point& p,const Point& a,const Point& b)
//point_to_line,点到直线距离,DistanceToLine
{
Vec v1=b-a,v2=p-a;
return fabs(cross(v1,v2)/len(v1));
}
double ptseg(const Point& p,const Point& a,const Point& b)
//point_to_segment,点到线段距离,DistanceToSegment
{
if(a==b) return len(p-a);
//Vec v1=b-a,v2=a-p,v3=p-b;
Vec v1=b-a,v2=p-a,v3=p-b;
if(dcmp(dot(v1,v2))<) return len(v2);
else if(dcmp(dot(v1,v3))>) return len(v3);
else return fabs(cross(v1,v2)/len(v1));
}
double area2(const Point& a,const Point& b,const Point& c)
//叉积对应平行四边形的面积
{
return cross(b-a,c-a);
}
double thrarea(const Point& a,const Point& b,const Point& c)
//三角形面积，绝对值
{
return fabs(cross(b-a,c-a)/);
}
bool ifpar(const Vec& a,const Vec& b)
//ifParallel
//是否共线/平行
{
return dcmp(cross(a,b))==;
}
Point pointline(const Point& p,const Point& a,const Vec& v)
//点在直线上投影,GetLineProjection
{
return a+v*(dot(p-a,v)/dot(v,v));
}
double sqr(double x){return x*x;}
double dis2(const Point &x,const Point &y)
{
return sqr(x.x-y.x)+sqr(x.y-y.y);
}
double len2(const Vec &x){return dot(x,x);}
};
using namespace X;
Point p[];
int n;
Point a;
double r2;
void make(const Point &x,const Point &y)
{
Vec t=(y-x)/;
a=x+t;
r2=len2(t);
}
void make(const Point &x,const Point &y,const Point &z)
{
Vec t1=(y-x)/,t2=(z-y)/;
Point x1=x+t1,y1=y+t2;
t1=normal1(t1);t2=normal1(t2);
a=lineline(x1,t1,y1,t2);
r2=dis2(a,x);
}
bool ok(const Point &x)
{
return dcmp(dis2(x,a)-r2)<=;
}
int main()
{
int i,j,k;
srand(time());
scanf("%d",&n);
for(i=;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
random_shuffle(p+,p+n+);
a=p[];r2=;
for(i=;i<=n;i++)
if(!ok(p[i]))
{
a=p[i];r2=;
for(j=;j<i;j++)
if(!ok(p[j]))
{
make(p[i],p[j]);
for(k=;k<j;k++)
if(!ok(p[k]))
{
make(p[i],p[j],p[k]);
}
}
}
printf("%.2f %.2f ",a.x,a.y);
printf("%.2f\n",sqrt(r2));
return ;
}