gistfile1.txt

#!/usr/bin/env python
import os
import math

pts = [(1,1), (0,0), (0.5, 0)]

def distance(p, p2):
    return math.sqrt((p[0]-p2[0])*(p[0]-p2[0]) + (p[1]-p2[1])*(p[1]-p2[1]))

def nearest(s, e):
    if s >= e:
        return float('inf'), None, None
    dist = float('inf')
    mid = s + (e - s) / 2

    p1 = None
    p2 = None

    d, t1, t2 = nearest(s, mid)
    if d < dist and t1 != None and t2 != None:
        dist = d
        p1, p2 = t1, t2

    d, t1, t2 = nearest(mid + 1, e)
    if d < dist and t1 != None and t2 != None:
        dist = d
        p1, p2 = t1, t2

    tmp = []
    for i in range(s ,e+1):
        if distance(pts[i], pts[mid]) < dist:
            tmp.append(pts[i])

    # sorted by y
    tmp = sorted(tmp, key=lambda x : x[1])

    for i in range(len(tmp)):
        for j in range(i+1, len(tmp)):
            d = distance(tmp[j], tmp[i])
            if d < dist:
                dist = d
                p1, p2 = tmp[i], tmp[j]

    return dist, p1, p2
    
pts = sorted(pts, key=lambda x : x[0])
d, p1, p2 = nearest(0, len(pts) -1)
print d,p1,p2