From 1d6a57ac37f0c56a7639c1124be5501f699f3027 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sun, 16 Dec 2018 20:21:12 -0600
Subject: Closest pair done!

I thought it wouldn't be this hard after I worked it out in Java first,
but once again it was fun and I learned a lot:
1. in all my previous exercises, my Python code performed better than my
Java code. This is the first time that my Java code significantly
outperforms my Python code: 0.92 seconds versus 7.93 seconds! My Java
code did use more than twice the memory.
2. Good re-enforcement of Python list copying concept, versus aliasing.
Don't forget the [:] (or [l:r]) magic!
3. list of (num, num) sort by first num by default, with proper tie
breaking. To sort on the second num, do list.sort(key=lambda x: x[1].
Cleve use of lambda, and it also does proper tie breaking.
4. I forgot to put this into my Java program comments, that Java code
gave me a good practice of comparator versus comparable interfaces,
which was very nice.

Fun stuff! Curious how much faster C++ program will be. I'll find out!---
 .../sources/closest_distance.py                    | 67 ++++++++++++++++++++++
 1 file changed, 67 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxPython/sources/closest_distance.py

(limited to 'AlgoDesignAndTechniqueEdxPython/sources/closest_distance.py')

diff --git a/AlgoDesignAndTechniqueEdxPython/sources/closest_distance.py b/AlgoDesignAndTechniqueEdxPython/sources/closest_distance.py
new file mode 100644
index 0000000..d394f2d
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/closest_distance.py
@@ -0,0 +1,67 @@
+# Uses python3
+import sys
+import math
+
+
+def distance(p1, p2):
+#     return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
+    return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2
+
+
+def baseCaseMinDistance(P, low, high):
+    if high - low == 1:
+        return distance(P[low], P[high])
+    if high - low == 2:
+        d1 = distance(P[low], P[low + 1])
+        d2 = distance(P[low], P[high])
+        d3 = distance(P[high], P[low + 1])
+        return min(d1, d2, d3)
+    if high - low == 3:
+        d1 = distance(P[low], P[low + 1])
+        d2 = distance(P[low], P[low + 2])
+        d3 = distance(P[low], P[high])
+        d4 = distance(P[low + 1], P[low + 2])
+        d5 = distance(P[low + 1], P[high])
+        d6 = distance(P[low + 2], P[high])
+        return min(d1, d2, d3, d4, d5, d6)
+
+
+def dPrimeDistance(shadedP):
+    minDistance = float('inf')
+    for i in range(len(shadedP)):
+        for j in range(1, 6):
+            if i + j < len(shadedP):
+                tempDistance = distance(shadedP[i], shadedP[i + j])
+                minDistance = min(tempDistance, minDistance)
+    return minDistance
+
+
+def minimalDistance(P, low, high):
+    if high - low <= 3:
+        return baseCaseMinDistance(P, low, high)
+    mid = int(low + (high - low) / 2)
+    midX = P[mid][0]
+    d1 = minimalDistance(P, low, mid - 1)
+    d2 = minimalDistance(P, mid, high)
+    d = min(d1, d2)
+    shadedP = [x for x in P[low:high] if abs(x[0] - midX) <= d]
+    shadedP.sort(key=lambda x: x[1])
+    dPrime = dPrimeDistance(shadedP)
+    return min(d, dPrime)
+
+
+def minDistance(X, Y):
+    P = []
+    for x, y in zip(X, Y):
+        P.append((x, y))
+    P.sort()
+    return math.sqrt(minimalDistance(P, 0, len(P) - 1))
+
+
+if __name__ == '__main__':
+    input = sys.stdin.read()
+    data = list(map(int, input.split()))
+    n = data[0]
+    x = data[1::2]
+    y = data[2::2]
+    print("{0:.9f}".format(minDistance(x, y)))
-- 
cgit v1.2.3