云里雾里的最小覆盖圆[完结]

思路

随机打乱所有点 初始化圆为1,2两个点为直径的圆 for i in (3,n+1) : if i不在当前圆内 : 设圆为1,i两个点为直径的圆 for j in (1,i) : if j不在当前圆内 : 设圆为j,i两个点为直径的圆 for k in (1,j) : if k不在当前圆内 : 设圆为i,j,k三个点确定的圆 在随机打乱的前提下,可以使用期望证明整个算法的复杂度是O(n)的。 ——keavil

几个关键定义

F[i]是P[1],P[2]…P[i]的最小覆盖圆
FF[j]是P[1],P[2]…P[j],P[i] 的最小覆盖圆,就是FF[j]是在i已经确定的情况下定义的
FFF[k]表示P[1]-P[k]∪P[i]并P[j]的最小覆盖圆

几乎都是改的LXY的代码Z]9F[T{S_F@JDH~KYDUHCQP

#include "cstring"
#include "cstdio"
#include "cmath"
#include "algorithm"
#include "cstdlib"
#include "iostream"
#define N 1100000
#define eps 1e-6
using namespace std;

struct point{
	double x,y;

	//点坐标快速赋值函数
	inline point(){}
	inline point(double X,double Y)
	{
		x = X;
		y = Y;
	}
	//重定义运算符
	inline point operator - (const point &t)const
	{
		return point(x - t.x,y - t.y);
	} 
	/*
		inline bool operator <(const point &t) const
		{
			return x < t.x;
		}
	*/
}p[N],T;

struct Cir
{
	point o;
	double r;

	inline double path(const point &A)//绝对距离
	{
		return sqrt(pow(A.x,2)+pow(A.y,2));
	}

	inline void get1(const point &A,const point &B)//以两点的path为直径的圆
	{
		o = point((A.x+B.x)/2,(A.y+B.y)/2);
		r = path(o-A);
	}

	inline void get2(const point &A,const point &B,const point &C)
	{
		double k1,b1,k2,b2;

		point m1,m2;//A-B B-C中点
		m1 = point((A.x+B.x)/2.0,(A.y+B.y)/2.0);//快速赋值
		m2 = point((B.x+C.x)/2.0,(B.y+C.y)/2.0);
		//P[8] = point(2,3) 快速点坐标赋值

		/*
			Warning!!!!
			万一 B.x = A.x 呢
			你就 /0 了!
			这是错误
			反正概率很小
			那就懒得改了
		*/

		k1 = (B.y-A.y)/(B.x-A.x);
		k1 = -1.0 / k1;
		k2 = (C.y-B.y)/(C.x-B.x);
		k2 = -1.0 / k2;

		b1 = m1.y - k1 * m1.x;
		b2 = m2.y - k2 * m2.x;

		o.x = (b2 - b1)/(k1 - k2);
		o.y = k1 * o.x + b1;
		r = path(A-o);
	}
}C,AA;

inline int sn(double x)
{
	return x < -eps ? -1 : x > eps ? 1 : 0;
}

inline bool in(const point &P,Cir C)
{
	double l = AA.path(P - C.o);
	return sn(l - C.r) <= 0;
	/*
		等价于
		if(sn(l - C.r) <= 0)
			return 1;
		else
			return 0;
	*/
}


int main()
{
	freopen("cir.in","r",stdin);
	//Init

	long long n;
	scanf("%lld",&n);
	for (long long i = 1; i <= n; i++)
		scanf("%lf%lf",&p[i].x,&p[i].y);
	
	//Solve

	//long long i,j,k;
	C.get1(p[1],p[2]);
	//printf("%lf %lf %lf\n", C.o.x,C.o.y,C.r);//first circle

	for (int i = 3; i <= n; i++)//跳过前3点
	{
		if (!in(p[i],C))//假如不在圆内
		{
			C.get1(p[1],p[i]);
			for (int j = 1; j <= i-1; j++)
			{
				if (!in(p[j],C))
				{
					C.get1(p[j],p[i]);
					for (int k = 1; k <= j-1; k++)
					{
						if (!in(p[k],C))
						{
							C.get2(p[j],p[k],p[i]);
							//printf("%lf %lf %lf\n", C.o.x,C.o.y,C.r);
						}
					}
				}
			}
		}
	}
	printf("%lf %lf %lf\n", C.o.x,C.o.y,C.r);
	return 0;
}

CC BY-SA 4.0 云里雾里的最小覆盖圆[完结] by 小小泥娃的部落格 is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

发表评论