|
||||||||||||||||||||||||
|
Заочный тур Московской городской олимпиады школьников по программированию
Задача E. Целые точки
| Имя входного файла: | e.in |
| Имя выходного файла: | e.out |
| Максимальное время работы на одном тесте: | 2 секунды |
| Максимальный объем используемой памяти: | 32 мегабайта |
Многоугольник (не обязательно выпуклый) на плоскости задан координатами своих вершин. Требуется подсчитать количество точек с целочисленными координатами, лежащих внутри него (но не на его границе).
Формат входных данных
В первой строке содержится N (3≤N≤1000) - число вершин многоугольника. В последующих N строках идут координаты (Xi, Yi) вершин многоугольника в порядке обхода по часовой стрелке. Xi и Yi - целые числа, по модулю не превосходящие 1000000.
Формат выходных данных
В выходной файл вывести одно число - искомое число точек.
Примеры
| e.in | e.out |
4 -1 -1 -1 1 1 1 1 -1 |
1 |
3 0 0 0 2 2 0 |
0 |