#from __future__ import division
from math import pow
from math import sqrt

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def show(self):
        return self.x, self.y

def calculateDistance(point1, point2):
	xDistance = point1.x - point2.x
	yDistance = point1.y - point2.y
	return sqrt(pow(xDistance, 2) + pow(yDistance, 2))

"Points"
points = []
points.append(Point(12, 12))
points.append(Point(103, 101))
points.append(Point(72, 74))
points.append(Point(0, 0))
points.append(Point(153, 101))


count = len(points)  # Amount of points

"I. Brute-force algorithm - O(n^2) time"
"http://e...content-available-to-author-only...a.org/wiki/Closest_pair_problem#Brute-force_algorithm"

print "\n", "I. BRUTE FORCE"
minimumDistance = float('inf')
for i in range(0, count):
	for j in range(i + 1, count):
		distance = calculateDistance(points[i], points[j])
		print "Distance between ", i, " and ", j, " is ", distance
		if distance < minimumDistance:
			minimumDistance = distance
print "Result: ", minimumDistance

print "\n", "#######################"

"II. Planar case - O(n log n) time"
"http://e...content-available-to-author-only...a.org/wiki/Closest_pair_problem#Planar_case"
print "\n", "II. PLANAR CASE"

"1. Sort points by X value"
points.sort(key=lambda point: point.x)
"sortedPoints = sorted(points, key=lambda point: point.x)"

"2. Split the set of points into two equal-sized subsets by X"
middle = count // 2  # Middle element's index
print "Middle index: ", middle

"3. Recursive function for step 4"
def rec(first, last):
	if first < last:
		rec(first + 1, last - 1)
		distance = calculateDistance(points[first], points[last])
		print "Distance between ", first, " and ", last, " is ", distance
		global minimumDistance # Hellish Satan! Damn Python scopes!
		global i
		global j
		if distance < minimumDistance:
			minimumDistance = distance
			i = first
			j = last

"4.1. Find the minimal distance in the left subset"
minimumDistance = float('inf')
rec(0, middle - 1)
leftMinimumDistance = minimumDistance
leftPointPair = (i, j)

"4.2. Find the minimal distance in the right subset"
minimumDistance = float('inf')
rec(middle, count - 1)
rightMinimumDistance = minimumDistance
rightPointPair = (i, j)

"5. Find the minimal distance among pairs in which one point lies on the left of the dividing vertical and the second point lies to the right"
averageMinimumDistance = float('inf')
for i in leftPointPair:
	for j in rightPointPair:
		# if i <> j:
		distance = calculateDistance(points[i], points[j])
		if distance < averageMinimumDistance:
			averageMinimumDistance = distance

"6. Find the minimal distance among three distances"
minimumDistance = min(leftMinimumDistance, rightMinimumDistance, averageMinimumDistance)

print "Result: ", minimumDistance