题目描述

JOI酱和IOI酱是好朋友。某天，JOI酱与IOI酱决定去山上的某个展望台进行天体观测。

从展望台上可以观测到$N$颗星星，编号为$1...N$。每颗星星的颜色为红色、蓝色、黄色中的一种。

在展望台上观测到的星星可以用坐标系上的点来表示。在坐标系上，星$i$（$1 \leq i \leq N$）对应的点为$P_i(X_i,Y_i)$。坐标系上的点两两不同，且不存在三点共线。

JOI酱和IOI酱想要设立一个叫做“JOIOI座”的星座。首先，两个人决定使用红色、蓝色、黄色三种颜色的星各一个构成的三角形。他们将这样的三角形称作“好三角形”。

两人将满足以下条件的好三角形无序二元组作为JOIOI座的候补：

1. 两个三角形没有公共点（包括内部和边界)。换言之，两个三角形之间既不相交，也不存在某个三角形包含另一个三角形。

JOI酱和IOI酱想知道构成JOIOI座的候补一共有多少种方案。

注意如果构成三角形的6个点一样但是构成三角形的方式不同，算作不同的方案。

现在给出展望台上能观测到的星星的信息，请求出构成JOIOI座的候补一共有多少种方案。

输入格式

第一行一个整数$N$，代表展望台上能观测到的星星的数量。 接下来$N$行，第$i$行（$1 \leq i \leq N$）有三个空格分隔的整数$X_i,Y_i,C_i$，表示星$i$的坐标为$P_i(X_i,Y_i)$，$C_i$表示星$i$的颜色，其中$0$代表红色，$1$代表蓝色，$2$代表黄色。

输出格式

输出一行一个整数，表示JOIOI座候补的方案数。

7
0 0 0
2 0 1
1 2 2
-2 1 0
-2 -3 0
0 -2 1
2 -2 2

4

数据范围

对于所有测试数据，$6 \leq N \leq 3000$，$-10^5 \leq X_i, Y_i \leq 10^5$（$1 \leq i \leq N$），$0 \leq C_i \leq 2$（$1 \leq i \leq N$）。

每种颜色的星至少存在一个。

$P_i \neq P_j$（$1 \leq i < j \leq N$）。

$P_i,P_j,P_k$不共线（$1 \leq i < j < k \leq N$）。

请注意你的常数。

题目来源

JOI 2013~2014 春季training合宿 竞技4 By PoPoQQQ