Given n pairs of points, how can we get the number of pair of points that can form a line with positive slope fast?
Then there are n lines, where the i-th line contains two integers xi and yi specifying the x and y-coordinates of i-th point. No two points have the same x-coordinate and no two points have the same y-coordinate.
My idea is to sort x first and then compare each point with the other below it. But it is still O(n^2)
Pick a point (randomly is easiest and has a good expected running time, although you can find a median point deterministically in linear time), split the axes into four quadrants:
x |
| x x
x | x
-----------x-----------
x |
x | x
| x
Denote the quadrants in counter-clockwise direction from top-left by I,II,III,IV:
II | I
----|----
III | IV
We shall disregard points that lie on the axes (edge case with theoretical probability of 0, and easily dealt with practically).
Note that all points in quadrant III form a positively-sloped line with all points in I, similarly no points from II will form p.s. lines with points in IV, so we recursively call:
NumPSLines(G) = |I|*|III| +
NumPSLines(I U II) +
NumPSLines(II U III) +
NumPSLines(III U IV)
Where U denotes union.
Assuming (proof left to reader) that the expected values E(|I|) = ... E(|IV|) = |G|/4 = n/4 and that the partition into quadrants is linear then we get an expected run time of:
T(n) = O(n) + 3T(n/2)
= O(n) + ... + 3^k * t(n/2^k) // where k = log2(n)
= O( log2(n) * 3^log2(n) )
= O(n^(log2(3)) * logn)
~ O(n^1.6 * logn)
Not sure if that bound is tight; haven't thought about it much.
This solution can be super optimised, although it's a start.
Sort descending by x and then count the number of inversions in y. Both steps are O(n log n).
Explanation: the number of (unordered) pairs with positive slope is the number of pairs {(xi, yi), (xj, yj)} such that xi > xj and yi > yj. When we sort descending by x, we make it so that xi > xj if and only if i < j. The definition of an inversion in the ys is a pair i < j such that yi > yj.
