e-olymp
Məsələlər

Подсчёт квадратов

Подсчёт квадратов

Вам задан многоугольник с вершинами с целочисельными координатами. Подсчитайте количество светлых и тёмных единичных квадратиков, полностью принадлежащих многоугольнику.

prb1701

Входные данные

Состоит из нескольких тестов (не более 25-ти). Каждый тест начинается количеством n (3n 100) вершин многоугольника. Следующие n строк содержат по два целых числа разделённых пробелом: x и y (0x10000, 0y10000) - координаты вершин многоугольника. Заканчиваются строкой с n = 0, которая не обрабатываться. Верхний левый угол имеет координаты (0, 0). Картинка выше соответствует первому тесту.

Выходные данные

Для каждого теста в отдельной строке выведите количество светлых и тёмных единичных квадратиков полностью принадлежащих многоугольнику в порядке убывания.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri
11
2 1
6 4
10 1
15 3
13 8
15 11
9 9
11 5
7 11
1 7
4 8
4
0 0
0 1
1 1
1 0
0
Çıxış verilənləri
27 25
1 0