Цілочисельні багатокутники#9441
Інгрід тримає магазин многокутників у далекій країні. Вона продає лише опуклі многокутники з цілочисловими координатами. Її покупці віддають перевагу многокутникам, які можна розрізати на дві половини правильним чином: розріз має бути прямим, має починатися й закінчуватися у вершинах многокутника, а обидві половини мають бути непорожніми та мати цілочислові площі. Що більше існує способів правильно розрізати многокутник, то він дорожчий.
Наприклад, лівий многокутник можна правильно розрізати трьома способами, а правий — двома.
Многокутники в магазині завжди відмінної якості, тому бізнес розширюється. Тепер Інгрід потрібен автоматичний інструмент для визначення кількості способів правильно розрізати многокутник. Це дуже важливо для її магазину, бо інакше вона витрачала б багато часу на встановлення цін — лише уявіть, скільки часу пішло б на те, щоб оцінити фургон середнього розміру, повний многокутників. Чи не могли б Ви допомогти Інгрід і написати для неї цей інструмент?
Перший рядок містить ціле число n~(4 \le n \le 200000) — кількість вершин многокутника. Кожен з наступних рядків містить координати вершини: два цілих числа x_i та y_i~(-10^9 \le x_i, y_i \le 10^9).
Заданий многокутник є опуклим, а його вершини перелічено в порядку обходу.
Виведіть одне ціле число : кількість способів правильно розрізати многокутник.
Приклад 1
Приклад 2