验证17维空间中通过三边和寻找最远三点方法的有效性

嘿，咱们先把两个核心问题理清楚：你的思路里的逻辑链条能不能站得住脚，还有你说的“最远三点”到底定义是什么。

你的思路里的核心误区：三边和最大≠面积最大的三角形 #

你一开始假设“最远三点连起来是面积最大的三角形”，然后想靠遍历所有三元组、取三边长度之和最大的来筛选，但这个逻辑其实不成立。给你举个直观的例子：

• 假设点集里有一对距离最远的点A和B（也就是点集的“直径”，距离记为D），第三个点C在AB的延长线上，离B点还有一段距离x。这时候三边和是 D + (D+x) + x = 2D + 2x，只要x够大，这个和能变得非常大，但三角形ABC的面积却是0——因为三点共线啊！
• 但如果有个点D在AB的垂直方向（17维空间里就是垂直于AB这条直线的子空间里），到AB的距离是h，这时候三边和是 D + 2*sqrt((D/2)² + h²)，这个和肯定比刚才的2D+2x小（只要x足够大），但三角形ABD的面积是 (1/2)*D*h，明显远大于0。

所以三边和最大的三元组，完全可能是面积趋近于0的共线点，根本不是面积最大的三角形，这一步的逻辑就断了。

那面积最大的三角形，是不是就是你要找的“最远三点”？ #

如果你的“最远三点”指的是能构成面积最大的三角形的三个点，那正确的思路应该是这样的：

1. 先找到点集的直径：也就是所有点对里距离最大的那两个点，记为A和B，它们的距离是D。
2. 遍历剩下的所有点C，计算C到直线AB的距离h（17维空间里可以用点积算投影，再用勾股定理推导：h = sqrt(|AC|² - (AC·AB/|AB|)²)）。
3. 挑h最大的那个点C，那么ABC就是面积最大的三角形——因为面积公式是(1/2)*D*h，D已经是最大的距离了，h最大的时候面积自然最大。

为什么一定要包含直径的两个点？简单说，如果存在一个三角形XYZ的面积比所有包含AB的三角形都大，那XYZ的底边XY的距离肯定≤D，那它的高h'得满足(1/2)*|XY|*h' > (1/2)*D*h_max，但|XY|≤D，这就要求h' > h_max，但h_max是所有点到AB的最大距离，这显然矛盾。所以面积最大的三角形必然包含直径的两个端点。

要是“最远三点”指的是两两距离都尽可能大的点？ #

如果你的目标不是面积最大，而是三个点之间两两距离都尽可能大（比如三个点两两的距离都是点集里的前几名），那这个问题和面积最大不完全等价，但通常最优的三元组也会包含直径的两个点，然后第三个点是离这两个点都比较远的。比如你可以先找到AB这对直径点，然后遍历所有点C，计算min(|AC|, |BC|)，取这个值最大的C——这样ABC的两两距离的最小值是最大的，三个点之间不会有太近的情况；或者也可以计算|AC| + |BC|最大的C，但要注意避开共线的点（毕竟共线的话面积为0，可能不是你想要的）。

最后给你捋捋思路的问题 #

你的思路有两个逻辑漏洞：

• 错误地把“三边和最大”和“面积最大的三角形”划了等号；
• 就算你要找面积最大的三角形，遍历所有三元组虽然可行（18个点的话总共C(18,3)=816个三元组，计算量不大），但不如先找直径再找最远点的方法高效，而且直接用三边和筛选完全不对，得直接计算每个三元组的面积才行。

内容的提问来源于stack exchange，提问作者Biscuit