constellation2

Constellation of Two

JOI and IOI are best friends. One day, JOI and IOI went to stargaze at an observatory on top of a mountain.

From the observatory, N stars are visible. Each star is numbered from 1 to N, and is either red, blue, or yellow in color.

The stars visible from the observatory can be represented as points on a coordinate plane. In this coordinate plane, the point corresponding to star \(i\) \((1 \leq i \leq N)\) is \(P_i(X_i, Y_i)\). No two of the points \(P_1, P_2, ... P_N\) are located at the same position, and no three points are collinear.

JOI and IOI decided they wanted to create a constellation, which they would name JOIOI. First, they thought of using a triangle to connect three stars of different colours: red, blue, and yellow. Such a triangle is called a good triangle.

The two of them decided that each pair of good triangles is a candidate for the JOIOI constellation, so long as they satisfy the following condition:

• The two good triangles (including perimeter and interior) share no common points. That is, the two good triangles do not intersect, nor is one enclosed with in the other.

JOI and IOI decided to count the number of possible candidates for the JOIOI constellation. Two constellation candidates are considered distinct if they have different good triangles, even if both of them are made from the same six stars.

Given a list of stars visible from the observatory, write a program that outputs the total number of candidates for the JOIOI constellation.

Input format

The first line of input consists of a single integer \(N\), the number of stars visible from the observatory.
\(N\) lines of input follow. The \(i^{th}\) of these lines contains 3 integers \(X_i\), \(Y_i\), and \(C_i\), denoting that the \(i^{th}\) star is located at \(P_i(X_i, Y_i)\), and has colour \(C_i\). The star is red if \(C_i\) is 0, blue if 1, and yellow if 2.

Output format

Output a single integer on a single line, the total number of candidates for the JOIOI constellation.

Limits

\(6 \leq n \leq 3000\).
\(-100000 \leq X_i, Y_i \leq 100000\).
There will be at least 1 star of each colour.
\(P_i \neq P_j\) \((1 \leq i < j \leq N)\)
\(P_i, P_j, P_k\) are not collinear \((1 \leq i < j < k \leq N)\).

Subtask #	Score	Constraints
1	15	\(n \leq 30\)
2	40	\(n \leq 300\)
3	45	No additional constraints

Samples

Sample Input 1	Sample Output 1
7 0 0 0 2 0 1 1 2 2 -2 1 0 -2 -3 0 0 -2 1 2 -2 2	4

In this input example, the stars are arranged as shown in the figure below. In this figure, the red stars are represented by circles, the blue stars by diamonds, and the yellow stars by triangles.

The four constellations satisfying the required conditions are:

Sample Input 2	Sample Output 2
8 16 0 0 17 0 0 0 7 2 0 -7 2 -1 -1 1 -1 1 2 -6 4 1 -6 -4 1	12

Sample Input 3	Sample Output 3
21 1 20 0 4 20 0 0 22 0 5 22 0 6 25 0 8 25 0 4 26 0 11 11 1 7 12 1 14 13 1 8 15 1 15 16 1 11 17 1 18 0 2 13 2 2 16 2 2 19 4 2 18 6 2 21 8 2 24 8 2 19 10 2	7748