diff options
author | Haidong Ji | 2018-12-16 20:21:12 -0600 |
---|---|---|
committer | Haidong Ji | 2018-12-16 20:21:12 -0600 |
commit | 1d6a57ac37f0c56a7639c1124be5501f699f3027 (patch) | |
tree | 922a96bbb6cf6d39aff7d494500f8f0d1956a38f /AlgoDesignAndTechniqueEdxPython/sources/closest_distance.py | |
parent | 88a15736625e2847d5c479ceabf202ea6be1e75b (diff) |
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!
Diffstat (limited to 'AlgoDesignAndTechniqueEdxPython/sources/closest_distance.py')
-rw-r--r-- | AlgoDesignAndTechniqueEdxPython/sources/closest_distance.py | 67 |
1 files changed, 67 insertions, 0 deletions
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))) |