Сайт підготовки до олімпіади з інформатики

Для вирішення завдання на визначення кількості цілих точок треба використовувати формулу Піка, яка записується так: x = s - n div 2 + 1, де s - площа багатокутника, n - кількість цілочисельних точок на його сторонах.
 Тобто нам необхідно знати площу багатокутника. Відома формула S = 1 / 2 * | (x1y2 - x2y1) + (x2y3 - x3y2) + ... + (xny1 - x1yn) |.

            Слід підрахувати кількість цілочисельних точок на сторонах багатокутника. Для цього треба порахувати довжину проекцій кожної сторони на координатні осі. Кількість точок на стороні - НСД довжин цих проекцій. НСД за алгоритмом Евкліда визначається так: на кожному кроці замінюємо найбільше з двох чисел на залишок ділення цього числа на менше, до тих пір, поки одна з чисел не стане рівним нулю. Число, що залишилося і є найбільший спільний дільник цих чисел. При підрахунку кількості точок слід також не забути порахувати відрізок, що з'єднує останню і першу точки багатокутника.
 Тепер ми вирахували все необхідне і залишилося тільки скористатися формулою, яка наведена на початку розбору: x = s - n div 2 + 1.