题面
\(n\) 个三维点 \((x_i,y_i,z_i)\),求两个距离最近的平行平面夹住所有点。输出距离。精度 \(10^{-9}\)。
\(1\le n\le 50, 1\le x_i,y_i,z_i\le 10^4\)。
原题可行解
两种 case:
- 答案平面平行于一个三点定平面;
- 答案平面平行于一对异面直线的公共平行面(例如:正四面体)。
前一种可以 \(O(n^3)\) 枚举平面,三维叉积求出法向量,这样每个点可以投影到这个法向量上。求一个法向量上的最大距离即可。
第二种可以 \(O(n^4)\) 枚举线段对,然后求出法向量,用和上面的一样的方法 \(O(n)\) 做一遍即可。
总共复杂度 \(O(n^5)\)。
不能过?常数 \(1/8\),其实可以过。
另解:较低复杂度但较低精度
这个大概是不能过了,就当理性愉悦。
其实也不知道对不对,毕竟没过,有误请指出。
考虑第二种 case 这么更快地做:取一条线段 \(ST\),作为新的 \(z\) 轴,然后任意找个 \(xOy\) 垂面,并设 \(S\) 为原点。将所有点投影至这个 \(xOy\) 平面上,就转化到一个二维平面上的问题:求一对最近的直线,夹住所有点。
然后就是求凸包 + 旋转卡壳。
这部分复杂度就是 \(O(n^3)\) 的了。
然而这样做精度就比较难搞了,\(10^{-5}\) 还差不多。
总结
还是对 \(10^{-9}\) 的恶意没有任何敏感度啊。
还是对自己代码里的常数没有任何推敲啊。
还是不会写几何啊。