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

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

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

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

Вхідні дані

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

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

3 \le n \le 2000,

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

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

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

Вихідні дані

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

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

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

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

  • \{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\}.