Pagini recente » Cod sursa (job #1168553) | Cod sursa (job #1687374) | Cod sursa (job #1871477) | Cod sursa (job #1182616) | Cod sursa (job #2521039)
import math
in_path = "cmap.in"
out_path = "cmap.out"
out_file = open(out_path, 'w')
str = open(in_path).read()
str = str.split('\n')
point = []
def dist(p1, p2):
return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)
def bruteforce(st, dre):
mn = float("inf")
for i in range(st, dre - 1):
for j in range(i+1, dre):
mn = min(mn, dist(point[i], point[j]))
return mn
def second(val):
return val[1]
def cmap(st, dre):
# print(point[st:dre])
if dre - st <= 3 :
# print(bruteforce(st, dre))
return bruteforce(st, dre)
mid = (st + dre) // 2
dl = cmap(st, mid)
dr = cmap(mid, dre)
d = min(dl, dr)
strip = []
for i in range(st,dre):
if dist(point[i], point[mid]) <=d :
strip.append(point[i])
strip.sort(key = second)
for i in range(len(strip) - 1):
for j in range(1, len(strip)):
if i != mid and j != mid :
if dist(strip[i], strip[j]) < d:
d = dist(strip[i], strip[j])
if strip[j][1] - strip[i][1] >= d:
break
#print(d)
return d
n = int(str[0])
for i in range(1, len(str)):
curr = str[i].split()
curr[0] = int(curr[0])
curr[1] = int(curr[1])
point.append(curr)
point.sort()
print(round(cmap(0, len(point)), 6), file=out_file)
out_file.close()