410412: GYM104018 E Следы на полях

E. Следы на поляхограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Айбек всегда знал, что «там» кто-то есть. И он даже знал, что «они» уже вступали в контакт с человечеством, причем не один раз. Ну точнее не знал, но был уверен в этом каждой частичкой своего разума — всё указывало на это.

Например, недавно Айбек наткнулся на фотографии поля, испещерённого полосами примятой травы в виде ломаной линии. «Это точно сообщение от них!» — подумал Айбек. Осталось лишь это сообщение расшифровать.

Айбек знает, что «они» общаются посредством треугольников (и никак иначе). Поэтому первым делом Айбеку нужно вычислить, сколько суммарно треугольников нарисовано на поле.

Так как вы — самый компетентный агроном из всех знакомых Айбека, он настоятельно просит вас вычислить суммарное количество различных невырожденных треугольников, образованных ломаной линией примятой травы на поле.

Ломаная линия — это набор точек $$$P_1$$$, $$$P_2$$$, $$$\dots$$$, $$$P_N$$$ и отрезков, проведенных между парами соседних точек $$$P_i$$$ и $$$P_{i + 1}$$$ $$$(1 \le i < N)$$$.

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

• На левом рисунке нет треугольников — ломаная $$$(1, 1)$$$, $$$(1, 6)$$$, $$$(1, 11)$$$, $$$(6, 6)$$$, $$$(1, 1$$$);
• На правом рисунке один треугольник — ломаная $$$(1, 1)$$$, $$$(1, 11)$$$, $$$(6, 6)$$$, $$$(1, 1$$$).

Невырожденным является треугольник, имеющий строго положительную площадь.

Два треугольника являются различными, если различаются их множества точек — вершин.

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

В первой строке задано целое число $$$N$$$ $$$(4 \le N \le 100)$$$ — количество точек в ломаной линии.

В следующих $$$N$$$ строках находится по $$$2$$$ целых числа $$$x_i$$$ и $$$y_i$$$ $$$(0 \le |x_i|, |y_i| \le 256; 1 \le i \le N)$$$ — координаты $$$i$$$-й точки.

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

Выведите единственное целое число — суммарное количество невырожденных треугольников, образованных ломаной линией.

ПримерыВходные данные

7
0 0
10 10
10 0
0 10
0 0
0 10
10 0

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

2

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

6
-5 -7
0 7
5 -7
-7 3
7 3
-5 -7

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

10

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

7
-5 0
1 1
3 3
3 3
-5 -5
7 7
0 -5

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

0

Примечание

Первый тестовый пример

Данная ломаная образует всего 2 различных треугольника:

1. $$$(0, 0)$$$, $$$(0, 10)$$$, $$$(5, 5)$$$;
2. $$$(10, 10)$$$, $$$(10, 0)$$$, $$$(5, 5)$$$.

Второй тестовый пример

Данная ломаная образует 10 треугольников:

• $$$5$$$ «малых» треугольников — «лучи» звезды;

  Пример «малого» треугольника: $$$(7, 0)$$$, $$$(\frac{-10}{7}, 3)$$$, $$$(\frac{10}{7}, 3)$$$;

• $$$5$$$ «больших» треугольников;

  Пример «большого» треугольника: $$$(-5, -7)$$$, $$$(\frac{-10}{7}, 3)$$$, $$$(7, 3)$$$;

Третий тестовый пример

В этом случае ломаная вообще не образует ни одного невырожденного треугольника.

Зато Айбек указал две одинаковые точки подряд $$$(3, 3)$$$ и несколько точек на одной и той же прямой.