Pagini recente » Cod sursa (job #3208667) | Cod sursa (job #3293374) | Cod sursa (job #3147804) | Rating Info-Oltenia 2018 (infooltenia) | Cod sursa (job #2458749)
import sys
f = open("cmap.in", 'r')
n = int(f.readline())
a = []
for _ in range(n):
line = f.readline().split()
x, y = int(line[0]), int(line[1])
a.append([x, y])
a = sorted(a, key=lambda x: x[0])
INF = float('inf')
def dist(x, y):
return (x[0]-y[0])**2 + (x[1]-y[1])**2
def fun(a):
if len(a) < 2 :
return INF
if len(a) == 2:
return dist(a[0], a[1])
m = len(a)//2
s = min(fun(a[:m]), fun(a[m:]))
mn = INF
points = [x for x in a if abs(x[0]-a[m][0]) <= s]
points = sorted(points, key=lambda x: x[1])
for i in range(len(points)):
j = i+1
while j<len(points):
d = dist(points[j], points[i])
mn = min(mn, d)
if points[j][1]-points[i][1] >= s:
break
j += 1
return min(mn, s)
f = open("cmap.out", 'w')
r = fun(a)
f.write(str(r**0.5))