D - さんかく Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

平面上に存在する N（N は 3 の倍数）個の点を用いて三角形を N/3 個作り、その面積の合計値を出来るだけ大きくするゲームがあります。
ただし、i（0≦i≦N-1）番目の点を示す X 座標の値 x_i と Y 座標の値 y_i はそれぞれ 0≦x_i≦100,000 と 0≦y_i≦100,000 を満たします。

高橋君はこのゲームをコンピュータを使って挑戦します。
しかし、彼は良いアルゴリズムが思いつかなかったため、ランダムで解くことにしました。

高橋君はランダムに 3 つずつ点を選び、N/3 個の三角形を作ります。
これを 1,000 万回行い、最も良かった答えを採用します。

貴方は、高橋君の解答と同じか、それよりより値が大きくなる解答を作りたいです。
そのような三角形の組み合わせを出力してください。

入力

入力は以下の形式で標準入力から与えられる。 
N
x_0 y_0
:
:
x_{N-1} y_{N-1}
  • 入力は N+1 行ある。
  • 1 行目には平面上の点の個数を表す整数 N\ (3≦N≦3,000) が与えられる。ただし、N は 3 の倍数である。
  • 2 行目から N+1 行目までの N 行は点の座標を示している。
    • i\ (0≦i≦N-1) 番目に与えられる座標 (x_i, y_i) は 0≦x_i≦100,000 かつ 0≦y_i≦100,000 の範囲でランダムに与えられる。
    • 0≦i≦N-1 と 0≦j≦N-1 を満たし、i≠j である 2 つの整数 i と j において、x_i≠x_j もしくは y_i≠y_j の少なくとも片方を満たすことが保証されている。

部分点

テストデータには以下に示す 4 種類のデータセットのいずれかが含まれており、それぞれ与えられる点の数である N の値が異なっている。
あるデータセットに対して、高橋君が選択した三角形の面積の合計値と等しい、もしくは大きい解答を出力できたとき、あなたはそのデータセットに対して 2 点を得ることができる。
  • level1 (各 2 点、10 個): N=9
  • level2 (各 2 点、10 個): N=18
  • level3 (各 2 点、15 個): N=300
  • level4 (各 2 点、15 個): N=3,000

出力

三角形の面積の合計値が高橋君の解答と同じか、もしくはそれより大きい解答となる三角形の組み合わせを、頂点となる番号で出力せよ。
各三角形の頂点となる番号を 1 行につき 1 つの三角形が構成されるように出力し、半角スペースで区切ること。
また各三角形を出力する順番、および 1 つの三角形における頂点の出力の順番は問わない。
なお、行の終端には改行が必要である。

入力例 1

9
0 0
1 0
2 0
0 1
1 1
2 1
0 2
1 2
2 2

出力例 1

3 7 2
4 8 1
6 0 5
  • 入力例 1 を図示すると、上図のようになります。
  • 入力例 1 に対して、高橋君のアルゴリズムでは、上図のように点を選択します。この例と同じ面積、もしくは面積の合計が大きい回答を出力してください。

入力例 2

18
0 0
1 0
2 0
0 1
1 1
2 1
0 2
1 2
2 2
0 3
1 3
2 3
0 4
1 4
2 4
0 5
1 5
2 5

出力例 2

11 0 15
3 7 10
6 16 5
2 17 9
12 14 1
8 13 4
  • 入力例 2 に対して、高橋君のアルゴリズムでは、上図のように点を選択します。この例と同じ面積、もしくは面積の合計が大きい回答を出力してください。