Страусові пристрасті#5774
Джонні нещодавно потрапив у халепу з страусом на ім'я Чак. Після того, як йому вдалося зібрати всіх утікачів-страусів, фермер замислився, як запобігти такому хаосу в майбутньому.
Джонні вирішив побудувати нове житло для птахів. Він встановив сторожових веж, кожна з яких обладнана прожекторами, та з'єднав їх електрифікованими дротяними загородами. Таким чином утворилося подвір'я у формі многокутника з вершинами, де й житимуть страуси. Для зручності спостереження він планує з'єднати деякі пари не суміжних веж перегородками, розділивши подвір'я на N-2 трикутні ділянки, створивши маленькі загоники для страусів. Важливо, що ці стіни мають повністю знаходитись всередині многокутника, а кожна ділянка має бути невиродженим трикутником (тобто мати ненульову площу).
Тепер фермеру потрібно вирішити, як розділити подвір'я. Допоможіть йому проаналізувати всі можливі варіанти встановлення перегородок. Джонні цікавлять два питання — одне простіше, а друге складніше. По-перше, він хоче знати, між якими парами веж можна поставити перегородку у якомусь із планів поділу. По-друге, скільки загалом існує можливих варіантів поділу подвір'я.
Перший рядок вхідного файлу містить число (3 \leq N \leq 300) — кількість веж.
Наступні рядків містять описи веж у порядку їх обходу. -й рядок містить два цілих числа x_i, y_i, що не перевищують 10^4 за модулем — координати -ї вежі.
Гарантується, що подвір'я утворює многокутник з ненульовою площею, який не має самоперетинів та самодотиків.
У першому рядку виведіть — кількість пар веж, між якими можна побудувати перегородку.
Далі виведіть пар номерів веж по одній у кожному рядку. У кожній парі номери мають бути у зростаючому порядку, а самі пари відсортовані спочатку за першим, потім за другим номером.
В останньому рядку виведіть одне число — кількість способів розділити подвір'я на ділянки. Оскільки ця кількість може бути великою, виведіть її по модулю 2^{30} = 1073741824.
Приклад 1