Трикутна оболонка

Обмеження: 3 сек., 512 МіБ

На площині задано \(n\) точок \(p_i\) з координатами \((x_i, y_i)\). Гарантовано, що жодні дві точки не збігаються, а жодні три точки не лежать на одній прямій.

Знайдіть кількість способів вибрати три точки із заданої множини так, щоб опукла оболонка будь-якої підмножини, яка містить ці три точки, була трикутником.

Вхідні дані

У першому рядку задано ціле число \(n\) — кількість точок.

У кожному з наступних \(n\) рядків задано по два цілі числа \(x_i\) та \(y_i\) — координати точки \(p_i\).

Вихідні дані

Виведіть одне ціле число — кількість способів вибрати три точки із заданої множини так, щоб опукла оболонка будь-якої підмножини, яка містить ці три точки, була трикутником.

Обмеження

\(3 \le n \le 2000\),

\(|x_i|, |y_i| \le 10^9\),

жодні дві точки не збігаються,

жодні три точки не лежать на одній прямій.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 2 7 0 9 -2 -2 9 4 3 3 -8 -10 -2 -3	2

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 -1 -1 1 -1 0 1 0 0	4

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 -50 -33 50 -31 -93 98 -47 -59 16 -35 79 -25 -75 41	15

Примітки

Точки з першого прикладу розташовані так, як показано на рисунку нижче.

У першому прикладі умову задовольняють такі два способи вибору трьох точок:

• \(\{p_1, p_4, p_6\}\),

• \(\{p_2, p_4, p_6\}\).

Точки з другого прикладу розташовані так, як показано на рисунку нижче.

У другому прикладі умову задовольняють такі чотири способи вибору трьох точок:

• \(\{p_1, p_2, p_3\}\),

• \(\{p_1, p_2, p_4\}\),

• \(\{p_1, p_3, p_4\}\),

• \(\{p_2, p_3, p_4\}\).