Pagini recente » Borderou de evaluare (job #1551141) | Cod sursa (job #3189896) | Cod sursa (job #169194) | Cod sursa (job #2322723) | Cod sursa (job #2522313)
import math
with open("cmap.in", "r") as f:
line = f.readline()
n = int(line.split(' ')[0])
points = []
for i in range(0, n):
line = f.readline()
points.append((int(line.split(' ')[0]), int(line.split(' ')[1])))
def distance(a, b):
return math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)
def smallestDistance(points, left, right):
if (right - left + 1 == 2):
if points[left][1] > points[right][1]:
points[right], points[left] = points[left], points[right]
return distance(points[right], points[left])
if (right - left + 1 == 3):
points[left: right + 1] = sorted(points[left: right + 1], key=lambda x: x[1])
return min(
distance(points[right], points[left]),
distance(points[left + 1], points[left]),
distance(points[right], points[left + 1])
)
mid = (left + right) // 2
midx = points[mid][0]
dist = min(smallestDistance(points, left, mid), smallestDistance(points, mid + 1, right))
# interclasarea punctelor
i = left
j = mid + 1
aux = []
while i <= mid and j <= right:
if (points[i][1] < points[j][1]):
aux.append(points[i])
i += 1
else:
aux.append(points[j])
j += 1
while (i <= mid):
aux.append(points[i])
i += 1
while j <= right:
aux.append(points[j])
j += 1
deltaRect = []
for i in range(left, right + 1):
points[i] = aux[i - left]
if (points[i][0] - midx <= dist and points[i][0] - midx >= -dist):
deltaRect.append(points[i])
for i, point in enumerate(deltaRect):
for j in range(i + 1, min(len(deltaRect), i + 8)):
if (distance(point, deltaRect[j]) < dist):
dist = distance(point, deltaRect[j])
return dist
sorted(points, key=lambda x: x[0])
dist = smallestDistance(points, 0, len(points) - 1)
with open("cmap.out", "w") as g:
g.write("{}".format(dist))