O problema aqui é encontrar um conjunto de todos os pontos inteiros que dá uma soma mínima sobre todas as distâncias de Manhattan a partir de um determinado conjunto de pontos!

Por exemplo:

permite ter um determinado conjunto de pontos {P1, P2, P3 ... Pn}

O problema básico é encontrar um ponto que diga que X teria soma mínima em todas as distâncias dos pontos {P1, P2, P3 ... Pn}.

isto é | P1-X | + | P2-X | + .... + | Pn-X | = D, onde D será mínimo sobre todos os X.

Movendo um passo adiante, pode haver mais de um valor de X satisfazendo a condição acima. isto é, mais de um X pode ser possível, o que daria o mesmo valor D. Portanto, precisamos encontrar todos esses X.

Uma abordagem básica que qualquer um pode pensar será encontrar a mediana de insumos e, em seguida, força bruta as coordenadas que são mencionadas emesta postagem

Mas o problema com essa abordagem é: se a mediana dá dois valores que estão muito separados, então terminamos brutos, forçando todos os pontos que nunca serão executados em determinado tempo.

Então, existe alguma outra abordagem que daria o resultado mesmo quando os pontos estão muito distantes (onde mediana dá um alcance que é da ordem de 10 ^ 9).