We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Geometry
  4. Meeting Point
  5. Discussions

Meeting Point

  • hopak63029
     + 0 comments

    For the Meeting Point challenge: With N≤1000, brute-force O(N²) works—pick each house as meeting point, sum Manhattan distances (|dx|+|dy|) to all houses, output the minimum sum.

    Python solution:

    import sys

input = sys.stdin.read
data = input().split()

N = int(data[0])
points = []
index = 1
for i in range(N):
    x = int(data[index])
    y = int(data[index + 1])
    points.append((x, y))
    index += 2

min_dist = float('inf')
for px, py in points:
    total = sum(abs(px - qx) + abs(py - qy) for qx, qy in points)
    if total < min_dist:
        min_dist = total

print(min_dist)

    Sample input (4 houses: (0,1) (2,5) (3,1) (4,0)) outputs 10. Handles large coords with int. TLE? Optimize sorting for medians but eval at points only.