문제
JOI와 IOI는 친구 사이이다. 어느 날, JOI와 IOI는 산 위에있는 전망대에서 밤하늘 관측을 하기로 했다.
전망대에서는 N개의 별을 관측할 수 있다. 각각의 별에는 1에서 N까지 번호가 붙어 있고, 각각의 별은 적색, 청색, 황색 중 하나의 색을 띄고 있다.
이 전망대에서 관측된 별은 좌표 평면상의 점으로 표시된다. 이 좌표평면에서 별 i (1 ≤ i ≤ N)에 대응하는 점은 Pi (Xi, Yi)이다. 좌표 평면상의 점 P1, ...,PN은 모두 다르다. 또한 점 P1, ..., PN이 한 직선 위에 세 점이 있는 경우는 없다.
JOI와 IOI는 JOIOI자리라는 별자리를 만들기로 했다. 우선 두 사람은 적색, 청색, 황색 3개의 별을 잇는 삼각형을 고려했다. 이러한 삼각형의 수를 좋은 삼각형이라고 하자. 두 사람은 다음의 조건을 만족시키는 두 좋은 삼각형 쌍(순서 상관 없이)을 JOIOI 자리의 후보로 결정했다.
2개의 좋은 삼각형(삼각형의 둘레 및 내부)에는 공유 점이 없어야 한다. 즉, 2개의 좋은 삼각형끼리 겹치거나 하나가 다른에 포함되는 것은 별자리가 될 수 없다.
조건을 만족하는 예
조건을 충족하지 못하는 경우
JOI와 IOI는 JOIOI자리의 후보가 얼마나 많은지 직접 세어보기로 했다. JOIOI자리의 후보를 구성하는 6개의 별이 같아도 다른 모양으로 별을 이었다면 다른 별자리라고 간주한다.
전망대에서 관측 된 별의 정보가 주어 졌을 때, JOIOI 자리의 후보 수를 출력하는 프로그램을 작성하라.
입력
첫 번째 줄에는 정수 N이 주어진다. 이것은 전망대에서 관측 된 별의 개수가 N임을 나타낸다.
다음 N개의 줄 중 i번째 줄(1 ≤ i ≤ N)에는 3개의 정수 Xi, Yi, Ci가 공백으로 구분되어 주어진다. 이것은 별 i의 좌표가 Pi (Xi, Yi)이고, 색이 Ci라는 것을 의미한다. 별 i의 색상은 Ci가 0이면 적색이며, 1이면 청색이며, 2면 노란색이다.
출력
표준 출력에 JOIOI 자리의 후보 수를 나타내는 정수를 한 줄에 출력하라.
[제한사항]
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).
예제
7
0 0 0
2 0 1
1 2 2
-2 1 0
-2 -3 0
0 -2 1
2 -2 2
4
로그인해야 코드를 작성할 수 있어요.