P6761 [BalticOI 2010] BEARs (Day1)

In this problem, $(a,b) \to (c,d)$ represents a line segment from $(a,b)$ to $(c,d)$.

You are given $N$ line segments of length $1$, defined as “marked segments”. Now there is a robber at point $(A,B)$, and he wants to go to $(0,0)$. The police may choose any point and block any one line segment around it. For example, if they choose point $(0,0)$, then one of the following segments will be blocked: $(-1,1) \to (1,1)$, $(-1,1)\to (-1,-1)$, $(-1,-1) \to (1,-1)$, $(1,-1) \to (1,1)$. However, among the segments that are blocked, there must not be any segment that is **directly connected** to a marked segment. For example, $(0,0) \to (0,2)$ and $(0,1) \to (0,3)$ are directly connected, but $(-1,1) \to (1,1)$ and $(0,0) \to (0,3)$ are not. The robber may reach points on a blocked segment, but he cannot leave by crossing the blocked segment. Find the maximum value $D$ of the robber’s minimum distance to $(0,0)$.

The first line contains two integers $A,B$, representing that the robber initially is at $(A,B)$. The second line contains one integer $N$, representing the number of marked segments. The next $N$ lines each contain four integers $X_1,Y_1,X_2,Y_2$, representing a marked segment $(X_1,Y_1) \to (X_2,Y_2)$.

Output one integer, representing the maximum value $D$ of the robber’s minimum distance to $(0,0)$.

#### Sample Explanation For sample $1$, as shown in the figure below:  The chosen point is $(0,0)$, and the blocked segment is $(1,1) \to (1,-1)$. #### Constraints For $100\%$ of the testdata, $|A|,|B|,|X_1|,|Y_1|,|X_2|,|Y_2| \le 10^6$, $0 \le N \le 500$. It is guaranteed that for each marked segment, $X_1=X_2$ or $Y_1=Y_2$. #### Note Translated from [BalticOI 2010 Day1 A BEARs](https://boi.cses.fi/files/boi2010_day1.pdf). Translated by ChatGPT 5