31489번 - Break a leg! 다국어

문제

For the first time, breakdance will be featured in the Olympics. And you get to participate! Well, you get to participate to the jury. . . More precisely, you get to build the table in front of which the jury will be seated: still, that is an impressive feat, congratulations!

Actually, the top of the table is already built: it is plane, has constant width and constant density, and its shape consists in the interior of an $N$-sided non-crossing polygon $P_1P_2 \dots P_N$ in which no three vertices are collinear (i.e., no line goes through three vertices or more). You have three table legs of same length and negligible width. Your task is to place them at distinct corners of the table so that the table remains stable when standing on these legs. In other words, you must choose three vertices $P_i,ドル $P_j$ and $P_k$ of the polygon such that the centre of gravity of the polygon lies in the interior of the triangle $P_iP_jP_k$ (and not on its boundary).

In how many different ways can you do this? If two ways of placing legs differ only by a permutation of the legs, they are not counted as different ways.

입력

The first line contains the number $N$. Then follow $N$ lines: the $i$^th of these lines contains two spaceseparated integers $x_i$ and $y_i,ドル which are the $x$-coordinate and the $y$-coordinate of the vertex $P_i$.

출력

The output should contain a single line, consisting of a single integer: the number of ways of placing legs such that the table remains stable.

제한

• 3ドル \le N \le 100,円 000$
• $-1,円 000,円 000 \le x_i \le 1,円 000,円 000$ and $-1,円 000,円 000 \le y_i \le 1,円 000,円 000$ for all $i \le N$
• whenever 1ドル \le i < j < k \le N,ドル the vertices $P_i,ドル $P_j$ and $P_k$ are not collinear
• the polygonal shape $P_1P_2 \dots P_N$ is non-crossing

힌트