Vizualizare sursă pentru „3832 - A - Manhattan de Buget”

== Cerinţa ==
Dându-se N puncte laticiale, care este distanța Manhattan de buget minimă dintre două puncte de coordonate a b respectiv x y cu proprietatea că a-y >= x-b?
== Date de intrare ==
Fișierul de intrare mman.in conține pe prima linie numărul N, iar pe următoarele n linii se află câte două numere, pe linia i se află coordonatele x respectiv y ale punctului i.
== Date de ieșire ==
Fișierul de ieșire mman.out va conține pe prima linie numărul M reprezentând valoarea cerută.
== Restricţii şi precizări ==
* 2 ≤ n ≤ 100.000
* coordonatele tuturor punctelor aparțin intervalului [-1.000.000.000, 1.000.000.000].
* Distanța Manhattan de buget dintre punctul cu coordonate a b si punctul de coordonate x y este a-x+b-y.
== Exemplul 1 ==
; mman.in

  3
  1 1
  2 3
  -1 -1
; mman.out

  3
== Explicație ==
Distanța minimă dintre două puncte se obține din punctele cu coordonate 1 1 și 2 3.
<br>


== Rezolvare ==
<syntaxhighlight lang="python" line>
def minimum_manhattan_distance(n, points):
    min_distance = float('inf')
    points.sort(key=lambda point: point[0] - point[1])
    
    for i in range(1, n):
        distance = points[i][0] - points[i-1][0] + points[i][1] - points[i-1][1]
        min_distance = min(min_distance, distance)
    
    return min_distance

def read_input(file_name):
    with open(file_name, 'r') as file:
        n = int(file.readline().strip())
        points = [tuple(map(int, line.strip().split())) for _ in range(n)]
    return n, points

def write_output(file_name, result):
    with open(file_name, 'w') as file:
        file.write(str(result))

def main():
    n, points = read_input("mman.in")
    result = minimum_manhattan_distance(n, points)
    write_output("mman.out", result)

if __name__ == "__main__":
    main()

</syntaxhighlight>