algorithm - 计算给定线的交点数

Question

我正在准备谷歌的电话面试，遇到了这个问题：

给定二维空间中的线列表，如何在小于 O(n^2) 的时间内计算交叉点的数量？

他们说被面试者给出了一个 O(n^2) 的解决方案，然后面试官问他是否可以找到一个更好的解决方案。

谢谢。

Answer 1

二维中的两条线要么相交一次，要么平行。如果没有平行线，则有 n*(n-1)/2 个交点。O(n log n) 解决方案是按斜率对线进行排序，然后扫描平行度，为找到的每组 m 个平行线减去 m*(m-1)/2。

当然，这忽略了浮点舍入的任何实际问题，但我假设如果需要考虑，问题中会提到这一点。