给定二维平面中 n 个点的坐标，找出形成直角三角形的三元组的数量
Given the co-ordinates of n points in 2-D plane, find the number of triplets that form right triangle
我显然可以通过蛮力来做到这一点，一个一个地选择所有的三胞胎并检查它们是否形成直角三角形。
但是什么是更优化的方式呢？想不出。
编辑：由于你们中的一些人指出了另一个看似与这个问题相似的问题，我仔细检查了答案，但我仍然无法弄清楚如何使用这些答案解决这个问题。
这将适用于 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)，那么你要在Slope[i,....]中寻找(b,-a)或(-b,a)。
要优化搜索，请保持数组 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))
注意 :
确保标准化斜率向量，即：
coordinate_a = (p,q)
coordinate_b = (r,s)
slope_vector(a,b) = (p-r,q-s)/distance(a,b)
直角三角形的交点：两个正交边的公共坐标。
我显然可以通过蛮力来做到这一点，一个一个地选择所有的三胞胎并检查它们是否形成直角三角形。 但是什么是更优化的方式呢？想不出。
编辑：由于你们中的一些人指出了另一个看似与这个问题相似的问题，我仔细检查了答案，但我仍然无法弄清楚如何使用这些答案解决这个问题。
这将适用于 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)，那么你要在Slope[i,....]中寻找(b,-a)或(-b,a)。
要优化搜索，请保持数组 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))
注意 :
确保标准化斜率向量，即：
coordinate_a = (p,q) coordinate_b = (r,s) slope_vector(a,b) = (p-r,q-s)/distance(a,b)直角三角形的交点：两个正交边的公共坐标。