実行時間制限: 2 sec / メモリ制限: 1024 MB
問題文
旅をこよなく愛するXは、N 個の都市を1日に1つずつ訪れて最初の都市に戻る巡回旅行の計画を立てようとしています。
具体的には、0日目にスタートの都市に宿泊し、1日目から N 日目間の毎日、今いる都市からその日に訪れる都市へ移動して観光と宿泊をします。
ここで、N 日目に訪れる都市はスタートの都市と決めています。
Xは管理しやすくするため各都市に 0 〜 N - 1 の番号を重複なくつけました。
しかし、訪れる順番をまだ決められていません。
歩くのが大好きなXは、都市間を徒歩で移動したいと考えています。
さらに、毎日の移動時間を一定にしてスケジュール管理を簡単にするために、1日の移動距離の分散を小さくしたいと考えています。
ここで、都市の位置、都市間の移動距離、移動距離の分散は次で定義されます。
- 番号 i の都市の座標は (x_{i},\ y_{i}) で表される。複数の都市が同一の座標に存在することもありうる。
- 都市間の移動距離はユークリッド距離で定義される。
- 分散 \(\mathit{variance}\) は、j 日目の移動距離を d_{j} 、移動距離の平均を \(\mathit{average}\) とすると、 \[ \mathit{variance} = \frac{1}{N} \sum_{j=1}^{N}(d_j - \mathit{average})^2 \] で定義される。
各都市の観光情報を収集するのに忙しいXの代わりに、移動距離の分散ができるだけ小さくなるような都市の訪問順を考えてあげてください。
各テストケースの得点および、この問題の得点は、次のように計算されます。
- 1つのテストケースの得点は、\(10^6\div(1+\mathit{variance})\) で計算された値の小数点以下を切り上げたものになります。
- テストケースは全部で 50 個あります。各テストケースの得点の合計が、この問題の得点になります。
入力
入力は以下の形式で標準入力から与えられます。
N x_{0} y_{0} \(\vdots\) x_{i} y_{i} \(\vdots\) x_{N-1} y_{N-1}
- N は訪れる予定の都市の数を表す整数で、N=200 を満たします。
- x_{i},\ y_{i} は番号 i の都市の座標を表す整数の組で、 0≤x_{i},\ y_{i}≤500 を満たします。
出力
i 行目に、 i 日目に訪れる都市の番号 c_{i} を出力してください。(c_{0} はスタートの都市です。)
c_{N}=c_{0} になるため、 c_{N} は出力しません。
c_{0} \(\vdots\) c_{i} \(\vdots\) c_{N-1}
テストケースの生成について
各都市の座標は一様ランダムに生成されています。
入力例1
4 98 76 456 432 390 67 123 456
注意: この入力はテストケースとしての制約を満たしていません。
出力例1
0 2 1 3
移動距離は順番に \(292.13\cdots, 370.91\cdots, 333.86\cdots, 380.82\cdots\)、
平均移動距離は \(344.43\cdots\)、分散は \(1218.01\cdots\) になり、スコアは \(821\) になります。
移動パスをビジュアライズした結果を以下に図示します。
短い移動距離のところを赤く、長い移動距離のところを青く、平均値に近い移動距離のところは緑に表示しています。
ジェネレータとテスターとサンプル入力データ
テストケースジェネレータ・テスター・サンプル入力データを次のリンクから提供しています。
ビジュアライザ
入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。
- このビジュアライザはデスクトップ版の Google Chrome および Mozilla Firefox の最新バージョン上で動作確認を行っています。全てのブラウザ環境で動作することを保証していません。特に、Internet Explorer 上では動作しないことが確認されています。
- このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
- このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。
ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。