2004/Contest/愛媛大会

Problem H : Inherit the Spheres †

問題概要 †

解法 †

個数の増減が生じるのは次の位置（z 座標）に限られる．

• ある球の上端，下端
• 2 つの球が結合，分離する点

ただし上記の位置で常に個数の増減が生じるとは限らない．たとえば別の球の内部にあるような場合は個数の増減が生じない．実際にはもっと複雑な場合もあることから，上記の位置をすべて計算した後，それぞれの位置から少しだけ上および下の位置で実際に切断して個数を調べる方法がもっとも単純かつ安全である．

あとはこれらの位置の z 座標を求めることを考えればよい．前者については説明するまでもない．後者については 2 つの球の交差部分は円になることから，その円の上端および下端の z 座標を適当な方法で計算すればよい．二分法などの数値計算法によって計算しても構わないし，円（交差部分）が 2 つの球の中心を通る直線に直交する平面上にあることに注目すれば数式による導出も可能だろう．［泉，4 Dec 2004］

議論・その他 †

入力例 †

3
100 100 100 80
200 200 200 120
140 140 140 20
3
100 115 100 17
100 94 100 10
124 94 100 21
0

出力は次のとおり．

6
110100
10
1101010100

• 方針に誤りがあったのでコードも含めて修正．［泉，4 Dec 2004］

ファイルを添付する †

izumi_H.cpp

H.cpp