Pagini recente » Cod sursa (job #2776074) | Cod sursa (job #2268827) | Cod sursa (job #1986412) | Cod sursa (job #1638869) | Cod sursa (job #2491672)
import math
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __repr__(self):
return str((self.x, self.y))
def distance(A, B):
return math.sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y))
def closestPair_brute(arr):
n = len(arr)
if n < 2:
return math.inf
minDist = distance(arr[0], arr[1])
for i in range(0, n - 1):
for j in range(i + 1, n):
if distance(arr[i], arr[j]) < minDist:
minDist = distance(arr[i], arr[j])
return minDist
def closestPair(sortedX, sortedY):
n = len(sortedX)
if n <= 3:
return closestPair_brute(sortedX)
mid = int(n/2)
xLeft = sortedX[0:mid]
xRight = sortedX[mid:n]
xMid = sortedX[mid].x
yLeft = []
yRight = []
n = len(sortedY)
for i in range(0, n):
if sortedY[i].x <= xMid:
yLeft.append(sortedY[i])
else:
yRight.append(sortedY[i])
distLeft = closestPair(xLeft, yLeft)
distRight = closestPair(xRight, yRight)
distMin = min(distLeft, distRight)
yStrip = []
for i in range(0, n):
if abs(xMid - sortedY[i].x) < distMin:
yStrip.append(sortedY[i])
closest = distMin
for i in range(0, len(yStrip)):
k = i + 1
while k < len(yStrip) and yStrip[k].y - yStrip[i].y < distMin:
if distance(yStrip[k], yStrip[i]) < closest:
closest = distance(yStrip[k], yStrip[i])
k += 1
return closest
points = []
with open("cmap.in") as f:
n = int(f.readline())
for i in range(0, n):
x, y = f.readline().strip().split()
x = int(x)
y = int(y)
points.append(Point(x, y))
f.close()
sortedX = sorted(points, key=lambda k: k.x)
sortedY = sorted(points, key=lambda k: k.y)
g = open("cmap.out", "w+")
g.write(str(closestPair(sortedX, sortedY)))
g.close()