Official

F - Silver Woods Editorial by evima


Let us fix \(r\).

Assume that there are two points, \(A\) and \(B\), on a plane. Let \(\text{dist}(A,B)\) be the distance of two points \(A\) and \(B\), then it can pass through between \(AB\) if \(2r≤\text{dist}(A,B)\), and it can’t if \(2r>\text{dist}(A,B)\). This is also true for a line and a point; let \(\text{dist}(A,B)\) be the distance between line \(A\) and point \(B\), then it can pass through between \(AB\) if \(2r≤\text{dist}(A,B)\), and it can’t if \(2r>\text{dist}(A,B)\).

Let us consider a graph, whose vertices are the lines and the nails, in which there is an edge between for each pair of vertices such that \(2r>\text{dist}(x,y)\). If the two lines are in the same connected component, obviously the circle cannot be moved from \((-10^9,0)\) to \((10^9, 0)\). Conversely, if the two lines are not in the same connected component, the circle can be moved from \((-10^9,0)\) to \((10^9, 0)\). (The route can actually be constructed by the right-hand rule.)

Therefore, this problem can be solved in a total of \(O(N^2\log N)\) time with the algorithm of finding the distances between every pair of vertices firsthand, and then adding edges between pairs of vertices in the increasing order of distances.

Sample Code (C++) : https://atcoder.jp/contests/abc181/submissions/17733698
Sample Code (Python) : https://atcoder.jp/contests/abc181/submissions/17733487

BONUS : In fact it can be solved in a total of \(O(N^2)\) time. Think about it.

posted:
last update: