binary-search-tree - 任何优雅的二叉搜索树算法来解决这个问题？

Question

我遇到了这个问题，并希望有一个快速的算法来解决它。

给定 2D 平面中的 n 个点（没有一个 x 值或 y 值等于另一个），找出形成正斜率线的所有点对的数量。（比如 (0,0) 和 (1 ,1)，正斜率为 45 度)

由于 n 很大（比如 60000），所以我需要一个优雅的算法来将它保持在 1 秒内。我知道用 O(n^2) 很容易做到这一点，但它只是变慢了，大约需要 30 秒。是否可以使用二叉搜索树来完成 nlogn 复杂性？

我感谢任何想在这方面启发我的人。

Answer 1

看起来你应该能够在数学上做到这一点..

每组 2 个点（我相信使用排列）将是正数或负数，如果它们是随机点，这意味着平均 50% 正数和 50% 负数。所以这将是对的数量/ 2。