本選問題: 配管問題

与えられた複数のポイントに対し、できるだけ短い配管接続と なるようなプログラムを書け。

接続の条件は以下の通りである。

1. ポイントは必ず整数座標上にあるものとする。
2. 配管はすべてのポイントを接続する。
3. 最短距離を得るために、必要ならジョイントを増やす ことが許される。ただし、ジョイントの座標値は整数とは限らない。

たとえば、次のような配管を考える場合、垂直、水平にのみ 配管するすることを想定すると、これ以上短い配管は存在しない。

しかし、新たにジョイントを追加し、斜めの配管を許すと、次のような配置が 考えられる。

後者の方が総配管長が短いことがわかる(ただし、この配管は最短ではない)。

入力仕様

  X0 Y0
  X1 Y1
  ...

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

  参考プログラム
  #include <stdio.h>
  ...
  int x, y;
  ...
  while(scanf("%d %d", &x, &y)!=EOF){
    ...
  }

出力仕様

  配管長の総合計
  部分配管の両端の座標 Xi Yi  Xj Yj
  ...　

• 出力は標準出力に書き出すこと。
• すべてのポイント、およびジョイント座標を出力すること。ただし、 ポイント、ジョイントの区別は不要である。
• 以下のような場合(○がポイント、●がジョイント)、配管は 3本となることに注意。

        〇
        ｜
        ｜ 
        ｜
        ●─────
        ｜
        ｜
        ｜
        〇
  

• 配管長、座標は小数点以下3桁までを有効とする。

  参考プログラム
  printf("%.3f\n", S);       /* S : 総配管長 */
  for(i=0; i<N; i++){     /* N : 総配管数 */
     /* (Xi, Yi)---(Xj, Yj) /* 
     printf("%.3f %.3f %.3f %.3f\n", Xi, Yi, Xj, Yj);
   }

数学関数の使用について

    double sqrt(double)

    #include <math.h>

使用機種

SGI Origin2000(300MHz、256プロセッサ、256GBメモリ)のうち、 56プロセッサ、14GBメモリを使用する。

コンパイラ、実行条件

• 並列化のために、MPIライブラリを使用。

     % cc pro.c -lmpi
  

• 実行

     % mpirun -np 57 ./a.out      -- 56+1(自分自身)
  

• 資源の衝突

  同時に2チームが同じ機種の上で競うため、CPU、メモリ等の 資源を奪い合う事態が生じないよう、あらかじめ、資源を 2つに分割して(割り当ての固定)実行を行う。

審査方法

• 本コンテストは高校生チームの優劣を競う。大学生チームは 直接高校生チームと対決することはない。
• 参加チームを４ブロックに分ける(ただし、大学生チームは別 ブロック)。4ブロック内で総あたりを行い、ブロック内の一位同士で、 トーナメントを行う。
• トーナメント一回戦敗者同士で、3位を争う。また、勝者同士で 1位、2位を争う。
• 特別賞は、勝敗とは別にユニークな解法を生み出したチームに 与えられる。
• ブロック内対戦、トーナメントそれぞれにおいて異なった データを使用する。

審査基準

接続条件に合致した答えを出したプログラムを対象に 15秒(壁時間)を制限時間とし、より配管長が短いプログラムを 上位とする。同じ長さの場合、壁時間が短い方を上位とする。

なお、

• 1ブロック2チームの場合は、3試合行い優劣をつける。
• 1ブロック3チームの場合、すべて1勝1敗の時は、壁時間の 合計の短い方を上位とする。