Problem : 370 - 4A. 星座

Problem Statistics

Solved Member: 3　　Submission: 7　　User Tried: 3

Statement:

(Suara - 星座)

某天你到了山上的觀景台看星星，在觀景台上總共看得到 N 顆紅、藍、黃色的星星，你將它們一一由 1 標號到 N，並且記錄每顆星星的顏色。

你將 N 顆星星標在平面上對應的座標 (Xi, Yi)。接著，為了方便觀察你想要將星星們畫成你想要的星座。首先，你希望找一個 6 顆星並滿足下面條件的星座：

● 將這6顆星分成3個點3個點，3點之間用線連成三角形。每個三角形三個點的顏色都不相同
● 兩個三角形不相交(交集面積為0)

由於星星太多了，你開始煩惱，究竟有幾種選星座的方法呢？

Input:Output:

第一行有一個整數 N，代表星星的數量。
接下來 N 行，每行有三個整數 Xi,Yi,Ci，代表這顆星星的座標為 (Xi,Yi)，顏色為 Ci。其中 Ci 為 "0,1,2" 分別代表星星的顏色為 "紅,藍,黃"。

限制：
6 ≤ N ≤ 3000
|Xi|, |Yi| ≤ 100000
0 ≤ Ci ≤ 2
每種顏色的星星都至少有一個
任三點不共線

Subtask 1：(15分)
N ≤ 30

Subtask 2：(40分)
N ≤ 300

輸出一個整數，代表有幾種畫成星座的方法

Sample Input:Sample Output:

SAMPLE A:
7
0 0 0
2 0 1
1 2 2
-2 1 0
-2 -3 0
0 -2 1
2 -2 2

SAMPLE B:
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

SAMPLE C:
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

SAMPLE A:
4

SAMPLE B:
12

SAMPLE C:
7748

HINT:

SAMPLE A 的示意圖如下，不同符號代表不同顏色的星星：

以下為 4 種可能的星座選法

Source:

2013/2014 JOI 合宿 4模（日本IOI國手考）

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	500ms	262144kb
0-2	500ms	262144kb
0-3	500ms	262144kb
1-1	500ms	262144kb	15
1-2	500ms	262144kb
1-3	500ms	262144kb
1-4	500ms	262144kb
1-5	500ms	262144kb
1-6	500ms	262144kb
1-7	500ms	262144kb
1-8	500ms	262144kb
1-9	500ms	262144kb
1-10	500ms	262144kb
1-11	500ms	262144kb
1-12	500ms	262144kb
2-1	500ms	262144kb	40
2-2	500ms	262144kb
2-3	500ms	262144kb
2-4	500ms	262144kb
2-5	500ms	262144kb
2-6	500ms	262144kb
2-7	500ms	262144kb
2-8	500ms	262144kb
2-9	500ms	262144kb
2-10	500ms	262144kb
2-11	500ms	262144kb
2-12	500ms	262144kb
3-1	6000ms	262144kb	45
3-2	6000ms	262144kb
3-3	6000ms	262144kb
3-4	6000ms	262144kb
3-5	6000ms	262144kb
3-6	6000ms	262144kb
3-7	6000ms	262144kb
3-8	6000ms	262144kb
3-9	6000ms	262144kb
3-10	6000ms	262144kb
3-11	6000ms	262144kb
3-12	6000ms	262144kb
3-13	6000ms	262144kb
3-14	6000ms	262144kb
3-15	6000ms	262144kb
3-16	6000ms	262144kb