Largest Empty Circle on a Segment (UVa Live Archive Europe - Southeastern - 2010/2011 Bucharest (Romania))Comments

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4818

問題

線分がN個ある。([0,L],0)のどこかを中心とした線分と交わらない円を書きたいのだが半径の最大値はいくらになるか？
1<=N<=2000
0<=L<=10000
-20000<=線分のx,y座標<=20000

解法

円の中心を(x,0)とした時の半径の大きさをf(x)とし、線分iだけを見た場合の半径をfi(x)とする。fi(x)は下に凸の関数になるので各fi(x)で最小値を取る場所で区間を分割すれば、その区間の中ではfi(x)は単調減少もしくは単調増加になる。各区間についてf(x)は上に凸の関数になるので3分探索が行えば答えは求まる。しかしこれでは遅すぎるので、その区間の中でf(x)が取りうる値の上界を求め、それと現在の答えと比べ枝刈りをした。また各区間に対して順番に3分探索するよりも、一度に全ての区間に対して3分探索をやった方が効率的に枝が刈れる。
上記の方法でもぎりぎり間に合ったが、答えを二部探索し各fi(x)についてその答え以上になる区間を求め、全ての区間の共通部分が空集合になるかどうかで計算するほうがスマート。