fork(1) download
copy 
  1. #from __future__ import division
  2. from math import pow
  3. from math import sqrt
  4.  
  5. class Point:
  6.     def __init__(self, x, y):
  7.         self.x = x
  8.         self.y = y
  9.     def show(self):
  10.         return self.x, self.y
  11.  
  12. def calculateDistance(point1, point2):
  13. 	xDistance = point1.x - point2.x
  14. 	yDistance = point1.y - point2.y
  15. 	return sqrt(pow(xDistance, 2) + pow(yDistance, 2))
  16.  
  17. "Points"
  18. points = []
  19. points.append(Point(12, 12))
  20. points.append(Point(103, 101))
  21. points.append(Point(72, 74))
  22. points.append(Point(0, 0))
  23. points.append(Point(153, 101))
  24.  
  25.  
  26. count = len(points)  # Amount of points
  27.  
  28. "I. Brute-force algorithm - O(n^2) time"
  29. "http://e...content-available-to-author-only...a.org/wiki/Closest_pair_problem#Brute-force_algorithm"
  30.  
  31. print "\n", "I. BRUTE FORCE"
  32. minimumDistance = float('inf')
  33. for i in range(0, count):
  34. 	for j in range(i + 1, count):
  35. 		distance = calculateDistance(points[i], points[j])
  36. 		print "Distance between ", i, " and ", j, " is ", distance
  37. 		if distance < minimumDistance:
  38. 			minimumDistance = distance
  39. print "Result: ", minimumDistance
  40.  
  41. print "\n", "#######################"
  42.  
  43. "II. Planar case - O(n log n) time"
  44. "http://e...content-available-to-author-only...a.org/wiki/Closest_pair_problem#Planar_case"
  45. print "\n", "II. PLANAR CASE"
  46.  
  47. "1. Sort points by X value"
  48. points.sort(key=lambda point: point.x)
  49. "sortedPoints = sorted(points, key=lambda point: point.x)"
  50.  
  51. "2. Split the set of points into two equal-sized subsets by X"
  52. middle = count // 2  # Middle element's index
  53. print "Middle index: ", middle
  54.  
  55. "3. Recursive function for step 4"
  56. def rec(first, last):
  57. 	if first < last:
  58. 		rec(first + 1, last - 1)
  59. 		distance = calculateDistance(points[first], points[last])
  60. 		print "Distance between ", first, " and ", last, " is ", distance
  61. 		global minimumDistance # Hellish Satan! Damn Python scopes!
  62. 		global i
  63. 		global j
  64. 		if distance < minimumDistance:
  65. 			minimumDistance = distance
  66. 			i = first
  67. 			j = last
  68.  
  69. "4.1. Find the minimal distance in the left subset"
  70. minimumDistance = float('inf')
  71. rec(0, middle - 1)
  72. leftMinimumDistance = minimumDistance
  73. leftPointPair = (i, j)
  74.  
  75. "4.2. Find the minimal distance in the right subset"
  76. minimumDistance = float('inf')
  77. rec(middle, count - 1)
  78. rightMinimumDistance = minimumDistance
  79. rightPointPair = (i, j)
  80.  
  81. "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"
  82. averageMinimumDistance = float('inf')
  83. for i in leftPointPair:
  84. 	for j in rightPointPair:
  85. 		# if i <> j:
  86. 		distance = calculateDistance(points[i], points[j])
  87. 		if distance < averageMinimumDistance:
  88. 			averageMinimumDistance = distance
  89.  
  90. "6. Find the minimal distance among three distances"
  91. minimumDistance = min(leftMinimumDistance, rightMinimumDistance, averageMinimumDistance)
  92.  
  93. print "Result: ", minimumDistance
Success #stdin #stdout 0.02s 6688KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
I. BRUTE FORCE
Distance between  0  and  1  is  127.287077113
Distance between  0  and  2  is  86.2786184405
Distance between  0  and  3  is  16.9705627485
Distance between  0  and  4  is  166.739317499
Distance between  1  and  2  is  41.1096095822
Distance between  1  and  3  is  144.256715615
Distance between  1  and  4  is  50.0
Distance between  2  and  3  is  103.247275993
Distance between  2  and  4  is  85.3814968245
Distance between  3  and  4  is  183.330303005
Result:  16.9705627485

#######################

II. PLANAR CASE
Middle index:  2
Distance between  0  and  1  is  16.9705627485
Distance between  2  and  4  is  85.3814968245
Result:  16.9705627485
https://ideone.com/W9g4d
language:
Python (cpython 2.7.16)
created:
14 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!