Triangle Hull

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

There are \(n\) points \(p_i\) on a two-dimensional plane, with \(p_i\) located at coordinates \((x_i, y_i)\). It is guaranteed that no two points occupy the same position, and no three points are collinear.

Find the number of ways to choose three points from the given set such that the convex hull of any subset containing these three points is a triangle.

Вхідні дані

The first line contains an integer \(n\) – the number of points.

Each of the next \(n\) lines contains two integers \(x_i\) and \(y_i\) – the coordinates of \(p_i\).

Вихідні дані

Output a single integer – the number of ways to choose three points from the given set such that the convex hull of any subset containing these three points is a triangle.

Обмеження

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

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

no two points are at the same location,

no three points are collinear.

Приклади

Вхідні дані (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

Примітки

The given points in the first sample are arranged as shown in the figure below.

In the first sample, the following two ways to choose three points satisfy the condition:

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

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

The given points in the second sample are arranged as shown in the figure below.

In the second sample, the following four ways to choose three points satisfy the condition:

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

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

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

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