eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Триангуляция Делоне

Триангуляция Делоне

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Триангуляцией некоторого набора точек на плоскости называется набор невырожденных треугольников, удовлетворяющий следующим свойствам:

  1. Вершинами треугольников являются только точки исходного набора. Каждая точка исходного набора является вершиной хотя бы одного треугольника.

  2. Два различных треугольника либо не имеют общих точек, либо имеют общую вершину, либо имеют общую сторону (но площадь их пересечения всегда равна 0).

  3. Любая точка, лежащая внутри выпуклой оболочки исходного набора точек, принадлежит хотя бы одному треугольнику (она может принадлежать нескольким треугольникам, если является их общей вершиной или принадлежит их общей стороне). (Выпуклой оболочкой некоторого набора точек называется наименьший выпуклый многоугольник, содержащий все эти точки).

Триангуляция называется триангуляцией Делоне, если, кроме того, для нее выполняется следующее условие:

  • Внутри окружности, описанной около любого треугольника из триангуляции, не лежит ни одна из исходных точек (точки могут лежать на окружности, в частности на ней, очевидно, лежат вершины рассматриваемого треугольника)

Для заданного набора точек найдите количество его триангуляций Делоне (две триангуляции считаются различными, если они отличаются хотя бы одним треугольником)

Входные данные

В первой строке входного файла находится число N – количество точек (3N30) исходного набора. Следующие N строк содержат по одной паре вещественных чисел – координаты соответствующей точки. Никакие три точки не лежат на одной прямой.

Выходные данные

Выведите в выходной файл количество различных триангуляций Делоне указанного набора точек.

Пример

Входные данные #1
4
0.0 0.0
1.0 0.0
0.0 1.0
1.0 1.0
Выходные данные #1
2