最小圆覆盖
定义
二维平面上有若干个点,找出一个最小半径的圆覆盖所有的点
- 最小覆盖圆是唯一的
- 若p不在s的最小覆盖圆内部,则p必在s的最小覆盖圆边上
- 随机化点,依次加入每一个点,如果在圆外那么找一个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即为长轴长度。