ABC181 F - Silver Woods (600)
円の連続な移動を考えるのは難しいので、各釘と通路が半径$ rの円を持っていると考える
始点から終点まで点が他の円の内側に入らないように移動できれば良い
円が始点から終点まで移動できない条件は上下の通路が重複している部分のある釘を辿って繋がっていること
半径$ rを二分探索で求める
上の条件でUnion-Find木を使って釘同士と通路を連結する
各連結成分で以下を試す
連結成分内に上下の通路が両方含まれている場合、通れないと言うことなのでNG
全ての連結成分で通れるならOK
連結成分の構築が$ O(N^2α(N)
通れるかの判定が$ O(N)
二分探索の回数が$ Nに依らず20回程度なので全体で$ O(N^2α(N)