答えに対して二分探索を行います。答えが一定値以下となるための条件は次の通りです。

• 長方形と二つの半円からなる以下のような図形が \(N\) 個ある。これらがすべて交わる点は存在するか？（下図は入力例 1, 2 に対応します。）

これは、\(2N\) 本の線分と \(2N\) 個の円の交点をすべて列挙し、\(N\) 本の線分からそれらへの距離を計算することで \(O(N^3)\) 時間で判定でき、かろうじて間に合います。

実装例 (C++)

P.S. A, B, D, E, Ex の原案でした。