Задача P. Морская метеорология ≡

Автор:И. Туфанов, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Метеорологическая станция обслуживает участок моря, имеющий форму многоугольника. Станция собирает данные с буёв, которые должны быть расположены в узлах квадратной решётки. Другими словами, следует провести горизонтальные и вертикальные линии, параллельные осям координат, с одним и тем же шагом, и разместить буи в точках пересечения, попадающих внутрь многоугольника. Кроме того, вершины многоугольника также должны попадать в узлы решётки.

Требуется по данному многоугольнику определить максимальный целочисленный шаг решётки, при котором выполняются приведённые выше условия, и вычислить количество буев, которые необходимо установить.

Рекомендуется рассмотреть частичные решения для следующих случаев

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

Во входном файле содержится число вершин многоугольника N. За ним следует N пар целых чисел xi yi, — координаты вершин многоугольника, перечисленных в порядке обхода. Граница многоугольника не имеет самопересечений, но многоугольник не обязательно является выпуклым.

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

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

Ограничения

3 ≤ N ≤ 100, −5000 ≤ xi, yi ≤ 5000

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3
-1 -1
-1 1
3 -1
 
2 4
2 
4
0 0  0 1  5 1  5 0
 
1 12
0.037s 0.007s 15