algorithm - 给定 N 个坐标为整数的点，找出平行线的数量

Question

1. nC2 将给出我们可以在 O(n^2) 复杂度中形成的行数。
2. 在 O(n^2) 复杂度中找到这些线的斜率并将它们存储在一个数组中，比如 x。
3. 以 O(n^2 logn) 的复杂度对 x 进行排序。
4. 在 O(n^2) 时间内搜索平行线。

我们可以做得更好吗？

如果我必须找出任意两条线是否平行怎么办？仅此而已。我们可以在不找到所有线的情况下做到这一点吗？

Answer 1

由于坐标是整数，可以用哈希表来存储N²个斜率；将它们表示为不可约分数。这应该将对等值的搜索限制为 O(N²)。