図面上の複数のポイントを最短距離でつなぐ配管接続を 求める。接続の条件として、
黒丸がポイントを表し、太線が配管を表す。正方形の一辺を 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本を予選通過の候補とする。