문제
오늘 밤은 하늘이 아주 맑다.
하늘이 어찌나 맑은지 밤하늘의 평면 위에 별이 무려 N개나 보인다!
게다가 별의 색깔이 빨강, 노랑, 파랑의 세 종류로 눈으로 구분이 될 정도이다.
특이하게도 별들 중 세 개의 별이 한 직선 위에 떠 있는 경우는 없었다.
석표는 별들을 가만히 보다가 별들을 이어 삼각형 별자리들을 만들어 보았다.
삼각형 별자리는 하늘에서 빨강, 노랑, 파랑 별들을 하나씩 골라 선분으로 이어 삼각형을 만든 것이다.
하지만 삼각형은 너무 찾기가 쉬워 금방 질려버린 석표는 쌍삼각형 별자리들을 만들기 시작했다.
쌍삼각형 별자리는 삼각형 별자리 두 개를 합친 별자리를 말하는 것이다.
이때 두 삼각형이 영역을 서로 공유하는 것은 쌍삼각형 별자리라고 부르지 않는다.
더 정확히, 밤하늘의 어떤 점도 두 삼각형에 동시에 들어가면 안된다.
또, 두 쌍삼각형을 이루는 별들이 같아도 선을 긋는 방법이 다르면 둘은 다른 별자리이다.
석표는 서로 다른 쌍삼각형 별자리들의 개수를 세다가 그만 잠이 들고 말았다!
푹 잠든 석표를 대신해서 여러분이 대신 밤하늘의 별자리 개수를 세주도록 하자!
입력
첫 줄에 N이 주어진다.
그 다음 줄부터 한 줄에 하나씩 각각 i번 별의 X좌표, Y좌표, 색깔을 의미하는 Xi, Yi, Ci가 주어진다.
출력
서로 다른 쌍삼각형 별자리의 수를 한줄에 출력하라.
<제한 조건>
6 <= N <= 3000
-100000 <= Xi, Yi <= 100000
0<=Ci<=2 (0, 1, 2가 각각 빨강, 노랑, 파랑을 의미한다.)
좌표가 같은 두 별은 없다.
세 별은 한 직선 상에 있지 않다.
전체 데이터의 30%는 N<=30을 만족함이 보장된다.
위의 데이터를 포함해 전체 데이터의 60%는 N<=300을 만족함이 보장된다.
예제 #1
7
0 0 0
2 0 1
1 2 2
-2 1 0
-2 -3 0
0 -2 1
2 -2 2
4
예제 #2
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
로그인해야 코드를 작성할 수 있어요.