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になる)。

ソースコード

帰省中に解いたので手許にソースコードがない。
後日上げます。