Точка принадлежит треугольнику, если она лежит в треугольнике или на его границе. Два треугольника не пересекаются, если на плоскости нет точки, принадлежащей обоим треугольникам.
Вам даны \(n\) точек на плоскости. Никакие две из них не совпадают, никакие три не лежат на одной прямой.
Найдите количество различных способов выбрать два непересекающихся треугольника с вершинами в данных точках. Два способа, отличающиеся только перестановкой первого и второго треугольника или перестановкой вершин в треугольниках считаются одинаковыми.
Выходные данные
Выведите одно целое число — количество способов выбрать два непересекающихся треугольника.
Примечание
В первом примере есть шесть пар непересекающихся треугольников, они показаны на рисунке ниже.
Остальные пары треугольников пересекаются, например так:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 1
2 2
4 6
4 5
7 2
5 3
|
6
|
|
2
|
7
0 -1000000000
-5 -5
5 -5
-5 0
5 0
-2 2
2 2
|
21
|