AOJ 1157 : 大玉転がし - arukukaの日記

直方体を直方体の底面を表現する線分4つ（反時計回り）と高さhで表現する。

コースも線分として捉えると、各直方体への距離が求めることができる。
このときの距離を d とすると、h >= d のとき、そこを通過できる最大半径は d　になる。

f:id:arukuka:20170604150802p:plain

それ以外の場合は以下のようになる。

f:id:arukuka:20170604150931p:plain

円に交わっている点は2点しかないので、ここから円を求めることはできない（たぶん）。
そこでrを[0,1000+eps)の範囲で二分探索して円が直方体の頂点(-d, h)を内包する
最小のrを求める（円の中心は(0, r)）。

この操作をすべての直方体に対して行い、
最小のrを出力すればACとなる。

直方体の底面がコースを内包するケース（サンプルケースの最後から2番目）に注意。
内包判定は反時計回りで表現した線分（ベクトル）を用い、全ての線分に対して
点（始点終点それぞれ）が左にあるかどうかを求めればよい。これは外積を使う。