¡El problema aquí es encontrar el conjunto de todos los puntos enteros que da una suma mínima sobre todas las distancias de Manhattan desde el conjunto de puntos dado!

Por ejemplo:

tengamos un conjunto dado de puntos {P1, P2, P3 ... Pn}

El problema básico es encontrar un punto, digamos X, que tenga una suma mínima sobre todas las distancias desde los puntos {P1, P2, P3 ... Pn}.

es decir, | P1-X | + | P2-X | + .... + | Pn-X | = D, donde D será mínimo sobre toda X.

Avanzando un paso más, puede haber más de un valor de X que satisfaga la condición anterior. es decir, más de una X puede ser posible, lo que daría el mismo valor D. Por lo tanto, debemos encontrar todas esas X.

Un enfoque básico que cualquiera puede pensar es encontrar la mediana de los insumos y luego forzar bruscamente las coordenadas que se mencionan enesta publicación

Pero el problema con este enfoque es: si la mediana da dos valores que están muy separados, entonces terminamos brutalmente forzando todos los puntos que nunca se ejecutarán en un momento dado.

Entonces, ¿hay algún otro enfoque que dé el resultado incluso cuando los puntos están muy separados (donde la mediana da un rango que es del orden de 10 ^ 9)?