iansong   3년 전

Ian과 Andy는 어느 날 산 위에 있는 천문대에서 천체 관측을 하기로 했다.

천문대에서는 N개의 별을 관측할 수 있다. 각각의 별에는 1부터 N까지 번호가 붙어 있고, 각각의 별은 빨강, 파랑, 노랑 중 한 가지 색을 띠고 있다.

이 천문대에서 관측된 별은 좌표 평면상의 점으로 표현된다. 이 좌표 평면에서 별 i (1 ≤ i ≤ N)에 대응하는 점은 Pi(Xi, Yi)이다. 좌표 평면상의 점 P1, . . . , PN 은 어느 두 점도 다르다. 또한, 점 P1, . . . , PN 은 어느 3점도 동일선상에 있지 않다.

Ian과 Andy는 Iandy자리라는 별자리를 만들기로 했다. 먼저 두 사람은 빨강, 파랑, 노랑 세 개의 별을 연결한 삼각형을 사용하기로 했다. 이러한 삼각형을 좋은 삼각형이라고 한다. 두 사람은 다음 조건을 만족하는 두 개의 좋은 삼각형 쌍(순서는 상관없다)을 Iandy자리의 후보로 삼기로 했다.

두 개의 좋은 삼각형(삼각형의 둘레와 안쪽)에는 공유점이 없다. 즉, 두 개의 좋은 삼각형이 서로 겹치거나 한 삼각형이 다른 삼각형에 포함되지 않는다.

좋은 삼각형의 예

좋은 삼각형이 아닌 예

Ian과 Andy는 Iandy자리의 후보로 생각할 수 있는 것이 몇 개나 되는지 세어보기로 했다. 그러나 Iandy자리의 후보를 구성하는 6개의 별이 일치하더라도 좋은 삼각형을 이루는 방법이 다른 경우, 그것들을 다른 후보로 계산하기로 한다.

천문대에서 관측된 별들의 정보가 주어졌을 때, Iandy자리 후보의 총 개수를 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 천문대에서 관측한 별의 개수 N이 주어진다.

이어지는 N개의 줄 중 i번째 줄(1 ≤ i ≤ N)에는 3개의 정수 Xi, Yi, Ci가 공백을 사이에 두고 쓰여 있다. 이는 별 i의 좌표가 Pi(Xi, Yi)임을 나타내며, Ci는 별 i의 색을 나타낸다. 별 i의 색은 Ci가 0이면 빨간색, 1이면 파란색, 2이면 노란색이다.

출력

Iandy자리의 후보의 총 개수를 나타내는 정수를 한 줄에 출력한다.

제한

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 N ≤ 30을 만족한다.

2 N ≤ 300을 만족한다.

3 추가적인 제한은 없다.

예제 입력 1

이 예시에서 별의 배열은 아래 그림과 같다. 이 그림에서 빨간색 별은 원, 파란색 별은 마름모, 노란색 별은 삼각형으로 나타낸다.

이 입력 예에서 Iandy 자리의 후보 별은 아래와 같이 4 개이다.

댓글을 작성하려면 로그인해야 합니다.