星間広告計画

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

요약
3차원 공간의 서로 다른 N개 점 가운데 넓이가 양수인 직사각형의 네 꼭짓점이 되는 네 점의 조합 수를 센다.
난이도

보통10점 중 7점

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

문제

20XX 年，民間人の宇宙旅行が当たり前となった時代のことである．旅行会社の社長であるあなたは新たに小星団 X を発見した．小星団 X は N 個の小さな星からなり，星 i は 3 次元 xyz 直交座標系における (xi, yi, zi) の位置に存在している．

さて，あなたは星団 X 内に自分の会社の看板を建てようと計画している．具体的には，星団 X 内から同一平面上に存在する 4 つの相異なる星を選択し，それらの星を頂点とする正の面積を持つ長方形の看板を建てたいと考えている．ただし星の大きさは無視でき，長方形領域の周上や内部に別の星が存在しても問題ないとする．

看板の頂点となりうる 4 つの星の組の総数を求めよ．

입력

入力は 30 個以下のデータセットからなる．各データセットは次の形式で表される．

N

x1 y1 z1

⋮

xN yN zN

1 行目には整数 N が与えられる．N は星団 X に含まれる星の個数であり，4 ≤ N ≤ 1500 を満たす．

続く N 行には，星団 X に含まれる各星の座標が与えられる．このうち i 番目の行には整数 xi, yi, zi が与えられ，i 番目の星が 3 次元座標 (xi, yi, zi) の位置に存在していることを表す．|xi|, |yi|, |zi| ≤ 108 を満たすことが保証される．N 個の座標はすべて相異なる．

入力の終わりは 1 つのゼロからなる行で表される．

출력

各データセットについて，看板の頂点となりうる 4 つの星の組の総数を1 行で出力せよ．

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