Problem 1157 : Roll-A-Big-Ball
問題概要
日本語なので本文参照。(http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1157&lang=jp)
線分に沿って大玉を転がす。
平面上には直方体が、辺が各座標軸に平行なように、いくつか配置されている。
直方体にぶつからない大玉の最大のサイズを求めよ。
解法
線分と、各直方体のxy平面上の4つの辺ごととの最短距離だけを考えればよい。
そのような部分の断面について図を書くと、問題文の図E-1のような2通りの位置関係がありうるので、
それぞれ場合分けして求める。
最後に全ての最小値を取ればよい。
玉を転がす線分が、完全に直方体の内部に含まれる場合は別途場合分けが必要となる(答えは0になる)。