与えられた複数のポイントに対し、できるだけ短い配管接続と なるようなプログラムを書け。
接続の条件は以下の通りである。
たとえば、次のような配管を考える場合、垂直、水平にのみ 配管するすることを想定すると、これ以上短い配管は存在しない。
しかし、新たにジョイントを追加し、斜めの配管を許すと、次のような配置が 考えられる。
後者の方が総配管長が短いことがわかる(ただし、この配管は最短ではない)。
X0 Y0
X1 Y1
...
参考プログラム
#include <stdio.h>
...
int x, y;
...
while(scanf("%d %d", &x, &y)!=EOF){
...
}
配管長の総合計
部分配管の両端の座標 Xi Yi Xj Yj
...
〇 | | | ●───── | | | 〇
参考プログラム
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文を含める。
#include <math.h>
SGI Origin2000(300MHz、256プロセッサ、256GBメモリ)のうち、 56プロセッサ、14GBメモリを使用する。
% cc pro.c -lmpi
% mpirun -np 57 ./a.out -- 56+1(自分自身)
同時に2チームが同じ機種の上で競うため、CPU、メモリ等の 資源を奪い合う事態が生じないよう、あらかじめ、資源を 2つに分割して(割り当ての固定)実行を行う。
接続条件に合致した答えを出したプログラムを対象に 15秒(壁時間)を制限時間とし、より配管長が短いプログラムを 上位とする。同じ長さの場合、壁時間が短い方を上位とする。
なお、