1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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)))
|
