Задачі
Точки у многокутнику
Точки у многокутнику
Многокутник на площині задано цілочисельними координатами своїх n вершин у декартовій системі координат. Потрібно знайти число точок з цілочисельними координатами, які лежать всередині многокутника (не на границі). Сторони многокутника одна з одною не дотикаються (за винятком сусідніх - у вершинах) і не перетинаються.
Вхідні дані
У першому рядку знаходиться число n, у наступних n рядках - пари чисел - координати точок (3 ≤ n ≤ 10000`, координати вершин цілі і по модулю не перевищують 1000000). Якщо з'єднати точки у заданому порядку, а також з'єднати першу та останню точки, отримаємо заданий многокутник.
Вихідні дані
Вивести одне число - шукану кількість точок.
Вхідні дані #1
4 -10 -10 -10 10 10 10 10 -10
Вихідні дані #1
361