Codeforces Gym 101981 D Country Meow 三维计算几何

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

题目大意

给出n个点的三维空间坐标,在空间内找任意一个点使得其距离这n个点中的最远的点的欧几里得距离最小。

题解

说实话,马上考期末了应该复习来着,但是总是感觉不写完这篇心里闷得慌……

这题实际上应该是个最小覆盖球,不过此篇博客不打算使用这种算法来做,这里介绍一种比较纯数学的方法去做。

我们假设我们选的点为P(x,y,z),

那么距离的平方的表达式一定为

如果固定其中的x,y,那么这个式子就是关于z的一个二次函数,且是有极小值的二次函数。

对于x,y当然也是同理的。

我们要求的就是所有距离的平方的最大值的最小值,于是就是求取极小值的一个过程。

众所周知二次函数是个单峰函数,最小值就是极小值,而单峰函数求极小值我们可以用三分来做。

但是这有三个变量(x,y,z)那怎么办?

上面说到如果其中两个固定了,那么不会对第三个变量取值后的函数值产生影响。

于是我们考虑可以使用三分套三分套三分(三层三分套在一起),由于每一层三分并不会影响另外两层三分,于是这个做法是正确的。

这个题没有卡精度,其实eps没有什么用处。

代码

#include <bits/stdc++.h>
using namespace std;
struct point{
	double x,y,z;
}p[105];
int n;
double eps = 1e-6;
double mix,miy,miz,mxx,mxy,mxz;
double calc3(double x,double y,double z){
	double ans = 0;
	for(int i = 1;i <= n;++i){
		double ret = 0;
		ret += (x - p[i].x) * (x-p[i].x);
		ret += (y - p[i].y) * (y-p[i].y);
		ret += (z - p[i].z) * (z-p[i].z);
		ans = max(ans,ret);
	}
	return ans;
}
double calc2(double x,double y){
	double l = miz  - eps,r = mxz + eps,midl,midr;
	double ans = 1e15;
	for(int cnt2 = 1;cnt2 <= 60;++cnt2){
		midl = l + (r-l)/3.0;
		midr = r - (r-l)/3.0;
		double retl = calc3(x,y,midl);
		double retr = calc3(x,y,midr);
		ans = min(ans,min(retl,retr));
		if(retl < retr){
			r = midr;
		}
		else{
			l = midl;
		}
	}
	return ans;
}
double calc(double x){
	double l = miy  - eps,r = mxy + eps,midl,midr;
	double ans = 1e15;
	for(int cnt1 = 1;cnt1 <= 60;++cnt1){
		midl = l + (r-l)/3.0;
		midr = r - (r-l)/3.0;
		double retl = calc2(x,midl);
		double retr = calc2(x,midr);
		ans = min(ans,min(retl,retr));
		if(retl < retr){
			r = midr;
		}
		else{
			l = midl;
		}
	}
	return ans;
}
int main(){
	cin >> n;
	mix = 1e6;miy = 1e6;miz = 1e6;
	mxx = -mix;mxy = -miy;mxz = -miz;
	for(int i = 1;i <= n;++i){
		cin >> p[i].x >> p[i].y >> p[i].z;
		mix = min(mix,p[i].x);mxx = max(mxx,p[i].x);
		miy = min(miy,p[i].y);mxy = max(mxy,p[i].y);
		miz = min(miz,p[i].z);mxz = max(mxz,p[i].z);
	}
	double l = mix - eps,r = mxx + eps,midl,midr;
	double ans = 1e15;
	for(int cnt = 1;cnt <= 60;++cnt){
		midl = l + (r-l)/3.0;
		midr = r - (r-l)/3.0;
		double retl = calc(midl);
		double retr = calc(midr);
		ans = min(ans,min(retl,retr));
		if(retl < retr){
			r = midr;
		}
		else{
			l = midl;
		}
	}
	printf("%.8lf",sqrt(ans));
	return 0;
}

 

Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00