Триангуляцией некоторого набора точек на плоскости называется набор невырожденных треугольников, удовлетворяющий следующим свойствам:
1) Вершинами треугольников являются только точки исходного набора. Каждая точка исходного набора является вершиной хотя бы одного треугольника.
2) Два различных треугольника либо не имеют общих точек, либо имеют общую вершину, либо имеют общую сторону (но площадь их пересечения всегда равна 0).
3) Любая точка, лежащая внутри выпуклой оболочки исходного набора точек, принадлежит хотя бы одному треугольнику (она может принадлежать нескольким треугольникам, если является их общей вершиной или принадлежит их общей стороне). (Выпуклой оболочкой некоторого набора точек называется наименьший выпуклый многоугольник, содержащий все эти точки).
Триангуляция называется триангуляцией Делоне, если кроме того для нее выполняется следующее условие:
4) Внутри окружности, описанной около любого треугольника из триангуляции, не лежит ни одна из исходных точек (точки могут лежать на окружности, в частности на ней, очевидно, лежат вершины рассматриваемого треугольника).
Для заданного набора точек найдите количество его триангуляций Делоне (две триангуляции считаются различными, если они отличаются хотя бы одним треугольником).
Входные данные
В первой строке вводится число N - количество точек (3 <= N <= 30) исходного набора. Следующие N строк содержат по одной паре вещественных чисел - координаты соответствующей точки. Никакие три точки не лежат на одной прямой.
Выходные данные
Выведите количество различных триангуляций Делоне указанного набора точек.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
0.0 0.0
1.0 0.0
0.0 1.0
1.0 1.0
|
2
|