Tag-计算几何

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

 2019-06-06 17:27:01 |  0 Comments  |  三分 计算几何

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

题目大意

给出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
Title - Artist
0:00