予選課題: 配管問題

図面上の複数のポイントを最短距離でつなぐ配管接続を 求める。接続の条件として、

  1. ポイントは必ず整数座標上にあるものとする。
  2. 配管はすべてのポイントを接続する。
  3. 2つのポイントを結ぶ時、配管は水平、あるいは、 垂直にのみ配置するものとする。
  4. 最短距離を得るために、必要ならジョイントを増やす ことが許される。
例を示す。

黒丸がポイントを表し、太線が配管を表す。正方形の一辺を 1とすると、この図における配管長さの総合計は、18である。

これに対し、白丸で表されるジョイント2個をこの図に追加して、配管 しなおすと、

に示すように、配管長の総合計は16になる。この問題の場合、 この長さが最短である。

入力データ

  X0 Y0
  X1 Y1
  ...

入力データは標準入力から読み込む。データは、各ポイントの X座標、Y座標を表す。両座標の区切りはTABコードとする。 なお、座標は左下隅を(0,0)とし、X座標≦100、Y座標≦100である。

出力結果

  配管長の総合計
  部分配管の両端の座標 Xi Yi  Xj Yj
  以下同様

出力に際しての注意

審査基準

接続条件に合致した答えを出したプログラムを対象に、 1分(CPU時間)を制限時間とし、より長さが短いプログラムを上位と する。同じ長さの場合、CPU時間が短い方を上位とする。この中で 上位10本を予選通過の候補とする。