AT_caddi2019_a 球の詰め込み

[problemUrl]: https://atcoder.jp/contests/caddi2019/tasks/caddi2019_a サイズ $ L\ ×\ L\ ×\ L $ の立方体型の容器がある。この容器に球を詰め込むゲームを行う。 容器内の点は直交座標系によって表され、容器の頂点の座標のうち一つは $ (0,\ 0,\ 0) $ であり、その頂点から最も遠い頂点の座標は $ (L,\ L,\ L) $ である。 詰め込める球は $ N $ 個あり、球 $ 1 $、球 $ 2 $、…、球 $ N $ と呼ばれる。球 $ i $ の半径は $ R_i $ である。 これらから好きなだけ球を選び、それぞれ容器内の好きな整数座標に配置する (すなわち、球の中心がその整数座標となるように配置する)。 このとき、球が宙に浮いてもよいが、球が容器からはみ出たり球同士が重なったりしてはならない (球と容器、または球同士が接するのはよい)。 球の配置に対し、あなたの点数を以下の総和として計算する。 - 基礎点: 球 $ i $ には基礎点 $ P_i $ が定められており、球 $ i $ を容器内に設置すると $ P_i $ 点を得られる。 - ボーナス点: 近くに配置することが好ましい球のペアが $ M $ 組与えられる。より具体的には、$ 4 $ つの整数の組 $ (A_i,\ B_i,\ C_i,\ D_i) $ が $ M $ 個与えられる。これらはそれぞれ、球 $ A_i $ と球 $ B_i $ を中心間のユークリッド距離が $ C_i $ 以下となるように容器内に配置すると $ D_i $ 点を得られることを表す。(距離が $ C_i $ を超えるような配置が禁止されはしない。) 点数をできるだけ多く得られる球の配置を考えよ。最適解を求める必要はない。

入力は以下の形式で与えられる。 > $ L $ $ N $ $ M $ $ R_1 $ $ P_1 $ $ R_2 $ $ P_2 $ $ : $ $ R_N $ $ P_N $ $ A_1 $ $ B_1 $ $ C_1 $ $ D_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ D_2 $ $ : $ $ A_M $ $ B_M $ $ C_M $ $ D_M $

配置における球 $ i $ の中心座標を $ (X_i,\ Y_i,\ Z_i) $ として、以下の形式で出力せよ。ただし、容器内に配置しない球の中心座標は $ (-1,\ -1,\ -1) $ とせよ。 > $ X_1 $ $ Y_1 $ $ Z_1 $ $ X_2 $ $ Y_2 $ $ Z_2 $ $ : $ $ X_N $ $ Y_N $ $ Z_N $ 以下の場合、*Wrong Answer* と判定される。 - 出力フォーマットが誤っている ($ X_i,\ Y_i,\ Z_i $ のいずれかが整数でない場合を含む)。 - 球が容器からはみ出ている。すなわち、容器内に配置した球 $ i $ について、$ X_i\ -\ R_i $, $ Y_i\ -\ R_i $, $ Z_i\ -\ R_i $ のいずれかが $ 0 $ 未満であるか、$ X_i\ +\ R_i $, $ Y_i\ +\ R_i $, $ Z_i\ +\ R_i $ のいずれかが $ L $ より大きい。 - 球同士が重なっている。すなわち、容器内に配置した $ 2 $ つの球 $ i $, $ j $ $ (i\

### 制約 - $ L\ =\ 1000 $ - $ N\ =\ 1000 $ - $ M\ =\ 100000 $ - $ 1\ ≦\ R_i\ ≦\ 200 $ - $ 1\ ≦\ P_i\ ≦\ 80000 $ - $ 1\ ≦\ A_i\ \ B_i $ であれば $ A_i $ と $ B_i $ の値を入れ替える。 - $ C_i $ は、$ R_{A_i}\ +\ R_{B_i}\ +\ 1 $ 以上 $ R_{A_i}\ +\ R_{B_i}\ +\ 200 $ 以下の整数としてランダムに決定される。 - $ D_i $ は、$ 1 $ 以上 $ 2R_{A_i}R_{B_i} $ 以下の整数としてランダムに決定される。 ### 採点 単一のテストケースにおける点数は、問題文で述べたように基礎点とボーナス点の総和として算出される。 テストケースは $ 50 $ ケース与えられ、すべてのテストケースの点数の総和がその提出の得点となる。 なお、テストケース example\_01 以外で $ 1 $ ケースでも出力が *Wrong Answer* と判定された場合、example\_01 以外のケースの点数はすべて $ 0 $ 点となる。 ### サンプルコード (C++) [サンプルコード](https://img.atcoder.jp/caddi2019/9ba3e86cb2b7fc70ac58060984a01872.zip) このコードをそのまま提出しても構いません。 ### Sample Explanation 1 \[入出力例(zip)\](https://img.atcoder.jp/caddi2019/8a480af5f45398c148881593a68ffe14.zip)