AT_rco_contest_2019_qual_a ツーリストXの旅行計画

[problemUrl]: https://atcoder.jp/contests/rco-contest-2019-qual/tasks/rco_contest_2019_qual_a 旅をこよなく愛する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\

$ i $ 行目に、 $ i $ 日目に訪れる都市の番号 $ c_{i} $ を出力してください。（$ c_{0} $ はスタートの都市です。） $ c_{N}=c_{0} $ になるため、 $ c_{N} $ は出力しません。 > $ c_{0} $ \\(\\vdots\\) $ c_{i} $ \\(\\vdots\\) $ c_{N-1} $

### テストケースの生成について 各都市の座標は一様ランダムに生成されています。 ### ジェネレータとテスターとサンプル入力データ テストケースジェネレータ・テスター・サンプル入力データを次のリンクから提供しています。 [ジェネレータ・テスター・サンプル入力データ](https://github.com/recruit-communications/rco-contest-2019/tree/master/qual_A/tester) ### ビジュアライザ 入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。 - このビジュアライザはデスクトップ版の [Google Chrome](https://www.google.co.jp/chrome/browser/desktop/index.html) および [Mozilla Firefox](https://www.mozilla.org/firefox/new/) の最新バージョン上で動作確認を行っています。全てのブラウザ環境で動作することを保証していません。特に、Internet Explorer 上では動作しないことが確認されています。 - このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。 - このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。 ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。 [ビジュアライザ](https://github.com/recruit-communications/rco-contest-2019/tree/master/qual_A/visualizer)