만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

성간 광고 계획

시간 제한8초메모리 제한1024 MB

요약
3차원 공간에 있는 N개의 별 중 네 꼭짓점이 모두 별이고 넓이가 양수인 직사각형의 개수를 데이터셋마다 구합니다.
난이도

보통10점 중 6점

유형
기하, 해시맵
정답자
아직 제출이 없습니다

문제

20XX년, 민간인의 우주여행이 당연해진 시대의 이야기이다. 여행사 사장인 당신은 새로운 작은 성단 X를 발견했다. 성단 X는 NN개의 작은 별로 이루어져 있고, 별 ii는 3차원 xyz 직교좌표계의 (xi,yi,zi)(x_i, y_i, z_i) 위치에 있다.

당신은 성단 X 안에 회사의 간판을 세우려고 한다. 구체적으로, 성단 X의 별 중 같은 평면 위에 있는 서로 다른 별 4개를 골라, 그 별들을 꼭짓점으로 하는 넓이가 양수인 직사각형 간판을 세우려 한다. 별의 크기는 무시할 수 있으며, 직사각형의 둘레나 내부에 다른 별이 있어도 상관없다.

간판의 꼭짓점이 될 수 있는 별 4개의 조합의 총수를 구하라.

입력

입력은 최대 30개의 데이터셋으로 이루어진다. 각 데이터셋은 다음 형식으로 주어진다.

N
x1 y1 z1
...
xN yN zN

첫 줄에는 정수 NN이 주어진다. NN은 성단 X에 포함된 별의 개수이며, 4≤N≤15004 \le N \le 1500을 만족한다.

이어지는 NN개의 줄에는 각 별의 좌표가 주어진다. i번째 줄에는 정수 xix_i, yiy_i, ziz_i가 주어지며, 이는 i번째 별이 3차원 좌표 (xi,yi,zi)(x_i, y_i, z_i)에 있음을 뜻한다. ∣xi∣,∣yi∣,∣zi∣≤108|x_i|, |y_i|, |z_i| \le 10^8을 만족함이 보장된다. NN개의 좌표는 모두 서로 다르다.

입력의 끝은 0 한 줄로 나타낸다.

출력

각 데이터셋에 대해, 간판의 꼭짓점이 될 수 있는 별 4개의 조합의 총수를 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    8
0 0 1
0 1 1
1 0 1
1 1 1
6 0 1
7 1 1
9 -1 1
8 -2 1
8
0 0 0
0 1 0
1 0 0
1 1 0
0 0 2
0 1 2
1 0 2
1 1 2
20
-2 -2 1
-2 -1 -2
-2 -1 1
-2 0 -2
-1 -2 -1
-1 1 -2
-1 1 1
-1 1 2
0 -2 -2
0 -2 -1
0 -2 1
0 1 2
0 2 -1
1 0 -2
1 0 -1
1 1 2
1 2 -1
1 2 0
2 1 -2
2 2 0
0
    예상 출력
    2
12
15