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

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

Задача B. Чёрно-белый поворот ≡

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

Условие

Чёрно-белое изображение состоит из h строк по w пикселей. Каджый пиксель имеет значение 0 или 1. С целью экономии памяти изображение было сжато следующим образом: для каждой строки сначала записывается значение первого пикселя, затем длины цепочек подряд идущих нулей и единиц. Например, строка 00100001110 будет закодирована последовательностью 0, 2, 1, 4, 3, 1.

Данное сжатое чёрно-белое изображение требуется повернуть на 90 градусов по часовой стрелке, и вывести, используя тот же метод сжатия.

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

Входной файл содержит числа w h, за которыми следует последовательность чисел, описывающая исходное изображение.

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

Выходной файл должен содержать последовательность чисел, описывающую повёрнутое изображение.

Ограничения

w, h ≥ 1, w × h ≤ 108, гарантируется, как исходное, так и повёрнутое изображение содержат в сжатом виде не более 106 чисел.

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3 3
1 3
1 1 1 1
0 2 1
 
0 1 2
0 2 1
1 3
2 
2 4
1 2  1 2  0 2  0 2
 
0 2 2
0 2 2
0.018s 0.003s 9