Break a leg!#11752
For the first time, breakdance will be featured in the Olympics. And you get to participate! Well, you get to participate in 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 -sided non-crossing polygon p_1p_2 \ldots 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~(3 \le n \le 10^5). Then follow lines: the -th of these lines contains two integers x_i and y_i~(-10^6 \le x_i, y_i \le 10^6), which are the -coordinate and the -coordinate of the vertex p_i.
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 \ldots p_n is non-crossing.
Print a single integer: the number of ways of placing legs such that the table remains stable.
Example 1
Example 2
Example 3