Dada la lista de puntos 2d, encuentra el punto más cercano a todos los demás puntos
Input: list of 2d points (x,y) where x and y are integers.
Distance: distance is defined as the Manhattan distance.
ie:
def dist(p1,p2)
return abs(p1.x-p2.x) + abs(p1.y - p2.y)
¿Qué es un algoritmo eficiente para encontrar el punto más cercano a todos los demás puntos?
Solo puedo pensar en una solución de fuerza bruta O (n ^ 2):
minDist=inf
bestPoint = null
for p1 in points:
dist = 0
for p2 in points:
dist+=distance(p1,p2)
minDist = min(dist,minDist)
bestPoint = argmin(p1, bestPoint)
Básicamente mira cada par de puntos.