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.

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>