Robber and the Barrier

A robber is located at point \((A,B)\) on the coordinate plane and intends to reach the origin \((0,0)\). In the plane there are also N marked segments, each of length \(1\). These segments (called marked lines) have fixed positions and their endpoints are given in the input. The police have a special tactic: at any chosen point they can close exactly one line segment among those emanating from that point. However, a segment that is directly connected (i.e. sharing an endpoint) with any marked line cannot be closed.

For example, consider the point \((0,0)\). Its four surrounding candidate segments are the four edges of the square with vertices \((-1,1)\), \((1,1)\), \((1,-1)\) and \((-1,-1)\); that is, the segments \[ (-1,1)\to (1,1),\quad (1,1)\to (1,-1),\quad (1,-1)\to (-1,-1),\quad (-1,-1)\to (-1,1). \] One of these may be closed by the police as long as neither of its endpoints is directly connected with a marked line. (For example, the segment \((0,0)\to(0,2)\) is considered directly connected to \((0,1)\to(0,3)\), while \((-1,1)\to(1,1)\) is not directly connected to \((0,0)\to(0,3)\).)

The robber can move to any point that lies on a closed segment, but he cannot cross a closed segment to get from one side to the other. In other words, if the police manage to form a complete closed barrier around the origin, the robber cannot enter the region that contains \((0,0)\).

The police strategy is to choose a barrier in the shape of a square (with sides parallel to the coordinate axes) that encloses the origin. For any positive integer \(r\) the candidate barrier is the square whose vertices are at \[ (-r,r),\ (r,r),\ (r,-r),\ (-r,-r). \] They will close each of the four boundary segments provided that neither endpoint of any of these segments is an endpoint of any marked line. Notice that if a marked segment has an endpoint that coincides with one of the square’s vertices then that boundary segment cannot be closed. Also, to successfully block the robber, the square must lie strictly between the robber and the origin; that is, the robber’s starting point \((A,B)\) must lie outside the square \([ -r, r ] \times [ -r, r ]\).

Your task is to help the police: Given the positions of the marked (immovable) segments and the starting point of the robber, determine the maximum value of \(D\) for which the police can form a barrier. Here \(D\) is defined as the largest positive integer \(r\) for which all four boundary segments of the square with vertices \((-r, r)\), \((r, r)\), \((r, -r)\), \((-r,-r)\) can be closed (that is, none of their endpoints coincides with an endpoint of any marked segment) and the robber’s starting point \((A,B)\) lies outside of the square \([ -r, r ] \times [ -r, r ]\). If no such barrier can be formed then \(D\) is \(0\).

Note on connection: Two segments are said to be directly connected if they share an endpoint.

inputFormat

The first line contains three integers \(N\), \(A\), and \(B\) \( (0 \le N \le 10^5,\; -10^9 \le A,B \le 10^9) \) representing the number of marked segments and the coordinates of the robber's starting point respectively.

Then follow \(N\) lines. Each of these lines contains four integers \(x_1\), \(y_1\), \(x_2\), \(y_2\) representing the endpoints of a marked segment. It is guaranteed that the distance between \((x_1,y_1)\) and \((x_2,y_2)\) is \(1\) and all coordinates are integers.

outputFormat

Output a single integer \(D\): the maximum possible value of \(r\) such that the police can form a complete barrier (i.e. all four boundary segments of the square with vertices \((-r, r)\), \((r, r)\), \((r, -r)\), \((-r, -r)\) can be closed) and the robber’s starting point \((A,B)\) lies outside the square \([ -r, r ] \times [ -r, r ]\). If no such barrier can be formed, output \(0\).

sample

1 2 3
0 0 1 0

2