시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
9 초 512 MB 2 2 2 100.000%

문제

JOI ちゃんと IOI ちゃんは親友同士である.ある日,JOI ちゃんと IOI ちゃんは山の上にある展望台で天 体観測をすることにした.

展望台では,N 個の星を観測することができる.それぞれの星には 1 から N まで番号が付いていて,そ れぞれの星は,赤色,青色,黄色のいずれかの色をしている.

この展望台で観測された星は座標平面上の点で表される.この座標平面において,星 i (1 ≤ i ≤ N) に対 応する点は Pi(Xi, Yi) である.座標平面上の点 P1, . . . , PN は,どの 2 点も異なる.また,点 P1, . . . , PN は, どの 3 点も同一直線上にない.

JOI ちゃんと IOI ちゃんは,JOIOI 座という星座を作ることにした.まず 2 人は,赤色,青色,黄色の 3 つの星を結んだ三角形を使うことを考えた.このような三角形のことを良い三角形と呼ぶ. 2 人は,以下の条件を満たす 2 つの良い三角形の組(順序を問わない)を JOIOI 座の候補とすることに した.

  • 2 つの良い三角形(三角形の周および内部)には共有点がない.すなわち,2 つの良い三角形同士が 重なったり,一方が他方に含まれることはない.

条件を満たす例

条件を満たさない例

JOI ちゃんと IOI ちゃんは,JOIOI 座の候補として考えられるものがいくつあるか数えることにした.た だし,JOIOI 座の候補を構成する 6 個の星が一致していても,良い三角形の結び方が異なる場合は,それ らを別の候補として数えるものとする.

展望台で観測された星の情報が与えられたとき,JOIOI 座の候補の総数を出力するプログラムを作成せよ.

입력

標準入力から以下のデータを読み込め.

  • 1 行目には整数 N が書かれている.これは展望台で観測された星の個数が N であることを表す.
  • 続く N 行のうちの i 行目 (1 ≤ i ≤ N) には,3 つの整数 Xi, Yi, Ci が空白を区切りとして書かれている. これは,星 i の座標が Pi(Xi, Yi) であることを表し,Ci は星 i の色を表している.星 i の色は,Ci が 0 なら赤色であり,1 なら青色であり,2 なら黄色である.

출력

標準出力に,JOIOI 座の候補の総数を表す整数を 1 行で出力せよ.

제한

  • 6 ≤ N ≤ 3 000.
  • −100 000 ≤ Xi ≤ 100 000.
  • −100 000 ≤ Yi ≤ 100 000.
  • 0 ≤ Ci ≤ 2.
  • どの色の星も 1 個以上存在する.
  • Pi ≠ Pj (1 ≤ i < j ≤ N)
  • Pi, Pj, Pk は同一直線上にない (1 ≤ i < j < k ≤ N).

예제 입력 1

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

예제 출력 1

4

この入力例では,星の配置は下図のようになる.この図において,赤色の星は丸,青色の星は菱型,黄 色の星は三角形で表す.

この入力例では,JOIOI 座の候補は以下に示す 4 つである.

条件を満たす 4 つの例

예제 입력 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

예제 출력 2

12

예제 입력 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

예제 출력 3

7748