最小圆覆盖


最小圆覆盖


定义

二维平面上有若干个点,找出一个最小半径的圆覆盖所有的点

  1. 最小覆盖圆是唯一的
  2. 若p不在s的最小覆盖圆内部,则p必在s的最小覆盖圆边上
  3. 随机化点,依次加入每一个点,如果在圆外那么找一个i在圆边上的圆,取最小值
for(int i=2;i<=n;i++)
	if(i不在圆内,i必在圆边上)
		圆<-Pi
		for(int j=1;j<i;j++)
			if(j不在圆内,则j在1-j-1,i且i在边上的最小圆边上)
			圆<-以pij为直径的圆
				for(int k=1;k<j;k++)
					if(k不在圆内,则必在圆边上)
					三点确定一个圆

模板

在一个二维平面上给定 N 个点,请你画出一个最小的能够包含所有点的圆。

第一行包含一个整数 N,接下来 N 行,每行包含两个实数,表示一个点的坐标 (Xi,Yi)。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define x first
#define y second
using namespace std;
typedef pair<double,double> PDD;
const int N = 1e5+10;
const double eps = 1e-12;
const double PI = acos(-1);
int n;
PDD q[N];
struct Circle
{
    PDD p;
    double r;
};
int sign(double x)
{
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}
int dcmp(double x,double y)
{
    if(fabs(x-y)<eps)   return 0;
    return x<y?-1:1;
}
PDD operator + (PDD a,PDD b)
{
    return{a.x+b.x,a.y+b.y};
}
PDD operator - (PDD a,PDD b)
{
    return{a.x-b.x,a.y-b.y};
}
PDD operator * (PDD a,double t)
{
    return {a.x*t,a.y*t};
}
PDD operator / (PDD a,double t)
{
    return {a.x/t,a.y/t};
}
double cross(PDD a,PDD b)
{
    return a.x*b.y-a.y*b.x;
}
double get_dist(PDD a,PDD b)
{
    double dx=a.x-b.x;
    double dy=a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}
PDD rotate(PDD a,double b)
{
    return {a.x*cos(b)+a.y*sin(b),-a.x*sin(b)+a.y*cos(b)};
}
PDD get_line_intersection(PDD p,PDD v,PDD q,PDD w)
{
    auto u=p-q;
    double t=cross(w,u)/cross(v,w);
    return p+v*t;
}
pair<PDD,PDD> get_line(PDD a,PDD b)
{
    return {(a+b)/2,rotate(b-a,PI/2)};
}
Circle get_circle(PDD a,PDD b,PDD c)
{
    auto u=get_line(a,b),v=get_line(a,c);
    auto p=get_line_intersection(u.x,u.y,v.x,v.y);
    return {p,get_dist(p,a)};
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)    scanf("%lf%lf",&q[i].x,&q[i].y);
    random_shuffle(q,q+n);
    Circle c({q[0],0});
    for(int i=1;i<n;i++)
        if(dcmp(c.r,get_dist(c.p,q[i]))<0)
        {
            c={q[i],0};
            for(int j=0;j<i;j++)
                if(dcmp(c.r,get_dist(c.p,q[j]))<0)
                {
                    c={(q[i]+q[j])/2,get_dist(q[i],q[j])/2};
                    for(int k=0;k<j;k++)
                        if(dcmp(c.r,get_dist(c.p,q[k]))<0)
                            c=get_circle(q[i],q[j],q[k]);
                }
        }
    printf("%.10lf\n",c.r);
    printf("%.10lf %.10lf\n",c.p.x,c.p.y);
    return 0;
}

椭圆

椭圆的做法是进行横向缩点,把椭圆按照离心率化为圆(x’^2+y’^2<=1)的形式(x’=x/p),所求的圆半径是短轴,圆半径乘p即为长轴长度。



文章作者: Dydong
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Dydong !
  目录