acm International Collegiate Programming Contest

Links

A B C D E F G H I

Problem C

星間広告計画

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

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

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

Input

入力は 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 つのゼロからなる行で表される.

Output

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

Sample Input

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

Sample Output

2
12
15
(End of Problem C) A B C D E F G H I