题面
\(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}\) 的恶意没有任何敏感度啊。
还是对自己代码里的常数没有任何推敲啊。
还是不会写几何啊。
标签：10,le,复杂度,CCPC,gap,2023,平面,Find,向量 From： https://www.cnblogs.com/Lice-wx/p/ccpc-2023-ol-j.html