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

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()