Триангуляція Делоне
Триангуляцією деякого набору точок на площині називається набір невироджених трикутників, який задовольняє наступним властивостям:
Вершинами трикутниуів є лише точки заданого набору. Кожна точка заданого набору є вершиною хоча б одного трикутника.
Два різних трикутника або не мають спільних точок, або мають спільну вершину, або мають спільну сторону (але площа їх перетину завжди дорівнює 0).
Довільна точка, яка лежить всередині опуклої оболонки заданого набору точок, належить хоча б одному трикутнику (вона може належати декільком трикутникам, якщо є їх пільною вершиною або належить їх спільній стороні). (Опуклою оболонкою деякого наборк точок називається найменший опуклий многокутник, який містить усі ці точки).
Триангуляція називається триангуляцією Делоне, якщо, крім того, для неї виконується наступна умова:
Всередині кола, описаного навколо довільного трикутника з триангуляції, не лежить жодна з заданих точок (точки можуть лежати на колі, зокрема на ньому, очевидно, лежать вершини розглядуваного трикутника).
Для заданого набору точок знайдіть кількість його триангуляцій Делоне (дві триангуляції вважаються різними, якщо вони відрізняються хоча б одним трикутником).
Вхідні дані
У першому рядку вхідного файлу знаходиться число N – кількість точок (3 ≤ N ≤ 30) заданого набору. Наступні N рядків містять по одній парі дійсних чисел – координати відповідної точки. Ніякі три точки не лежать на одній прямій.
Вихідні дані
Виведіть у вихідний файл кількість різних триангуляцій Делоне вказаного набору точок.