algorithm - 给定二维平面中 n 个点的坐标，找出形成直角三角形的三元组的数量

Question

我显然可以通过蛮力来做到这一点，通过一个接一个地选择所有三元组并检查它们是否形成直角三角形。 但是什么是更优化的方式呢？我想不出。

编辑:由于你们中的一些人指出了另一个看起来与这个问题相似的问题，我仔细检查了答案，但我仍然无法弄清楚如何使用这些答案解决这个问题。

Answer 1

这将适用于 O(n^2Log(n)) .

算法:

创建一个二维数组 Slope , 其中Slope[i,j]是 coordinate[i] 之间的斜率矢量和 coordinate[j] .

现在，对于 coordinate[i]作为直角三角形的关节(见注2)，Slope[i,....]中应该有两个斜坡它们彼此正交，即它们的点积为 0。

如果Slope[i,j] = (a,b) (in vector form) , 那么你必须寻找 (b,-a)或 (-b,a)在 Slope[i,....] .

为了优化搜索，保留数组 Slope[i,...]排序于 a或 b . 排序需要 O(nlogn)时间。

现在，对于任何Slope[i,j] , 进行二进制搜索以查找 (b,-a)和 (-b,a)在数组中。

二进制搜索所有 n斜坡需要O(nlogn)时间。

因此，总时间复杂度:

= Calculate slope between all points + Sort the slopes + BinarySearch 
= O(n*(n+nlogn+nlogn)) = O(n^2log(n)) 

注意:

1. 确保对斜率向量进行标准化，即:

   coordinate_a = (p,q) coordinate_b = (r,s) slope_vector(a,b) = (p-r,q-s)/distance(a,b)

2. 直角三角形的交点:两个正交边之间的公共(public)坐标。