Задача A. Длинный отрезок

Входной файл:input.txt   Ограничение времени:5 сек
Выходной файл:output.txt   Ограничение памяти:8 Мб

Условие

На плоскости задан многоугольник с целочисленными координатами вершин и сторонами, параллельными осям координат. Требуется найти самый длинный горизонтальный или вертикальный отрезок, лежащий внутри многоугольника. (Многоугольник включает свою границу).

Формат входного файла

В первой строке входного файла содержится число вершин N . В следующих N строках расположены целочисленные координаты вершин xi, yi, перечисленные в порядке обхода. (При этом у каждой пары соседних вершин либо координаты x, либо координаты y совпадают).

Формат выходного файла

Выходной файл должен содержать единственное целое число — длину самого длинного отрезка.

Ограничения

4 ≤ N ≤ 50 0 ≤ xi, yi ≤ 1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
8
15 10
20 10
20 20
40 20
40 5
60 5
60 50
15 50
45
2
8
10 50
20 50
20 0
30 0
30 60
20 60
20 80
10 80

80

0.149s 0.018s 13