Find the line guaranteed by Sylvester-Gallai
Python 2, not golfed

Sure, they say there's a worst case O(n*log(n)) algorithm, but who cares about the worst case? It's the average case we usually care about, and this simple random algorithm runs in expected linear time on arbitrary inputs! 

(By comparison, the deterministic brute force algorithm can be fed carefully constructed inputs to force it to run in quadratic time at least.)

import random,math
def radical_to_normal(x,y): return (x[1]**(1./x[0]),y[1]**(1./y[0]))

def distance_to_line(p1,p2,p3): 
 dx = p2[0] - p1[0]
 dy = p2[1] - p1[1]
 return abs(dy*p3[0] + dx*p3[1] + p2[0]*p1[1] - p2[1]*p1[0]) / math.sqrt(dy*dy + dx*dx)

points = input() #input as list of pairs
c = True
while c:
    c = False
    p1,p2 = random.sample(set(points), 2)
    for p3 in points:
        if distance_to_line(radical_to_normal(*p1), radical_to_normal(*p2), radical_to_normal(*p3)) &lt; 0.00001:
            c = True
print p1,p2


Example run:

➤ python sylvester.py
[((1,0),(1,0)),((1,1),(1,0)),((1,2),(1,0)),((1,0),(1,1)),((1,1),(1,1)),((1,2),(1,1)),((1,0),(1,2)),((1,1),(1,2)),((1,2),(1,2))]
((1, 2), (1, 2)) ((1, 0), (1, 1))


How it works

It's been proved (Csima and Sawyer 1993) that roughly 6/13 of all lines in any set are ordinary (only involve 2 points from the set) except when n=7. As the number of points goes to infinity, the lower bound goes to 1/2 of the lines (Green and Tao 2013). Therefore, we expect to have to test around 2-3 pairs of points on average before finding an ordinary line if we sample pairs of points at random.

This simple program just selects a random pair of points, then checks the distance from the line they form to a third point, which ranges over all points in the set. All three points are converted from radical root form to floats by radical_to_normal() before the distance is calculated by distance_to_line(). If the distance is below a threshold (indicating they are collinear), we set a sentinel to try again. Until every point tested passes above the threshold, we try, try again. (This threshold could be made much smaller and still work, of course.)

Since we test an expected constant number of point pairs, and we test n points for each pair, the algorithm runs in expected time O(n).