Shortest Path to the Altar

The ancient prophecy foretold that only a hero with unparalleled courage, strength, and especially wisdom could push a massive round stone into the center of the altar and break the seal protecting the fabled dragon‐slaying spear. In this problem, you are given the initial location of the stone’s center and the altar’s center. The stone is a circle of radius \(R\) and may roll in any direction. However, the temple is filled with stone pillars (which are right-angled prisms with square bases) that restrict the stone’s movement.

The stone may only be pushed if its center maintains a distance of at least \(R\) from every pillar during its journey. When this condition is violated, the pillar will block the motion. Your task is to compute the minimum route length necessary so that the stone’s center reaches the altar’s center (i.e. the two centers exactly coincide) while never coming closer than \(R\) to any pillar. If it is impossible to achieve this, output -1.

The problem naturally involves computational geometry: the safety condition is that for every pillar (given as an axis‐aligned rectangle with coordinates \(x_1, y_1, x_2, y_2\)), the Euclidean distance from any point on the stone’s path (its center) to the pillar must be at least \(R\). A point \((x,y)\) has distance to a rectangle defined by \([x_1,x_2]\times[y_1,y_2]\) computed as:

[ \text{dist}((x,y),[x_1,x_2]\times[y_1,y_2]) = \sqrt{\max(0, x_1 - x, x - x_2)^2 + \max(0, y_1 - y, y - y_2)^2}, ]

Your solution can be approached by constructing a visibility graph over a set of candidate points (including the start, target, and selected critical boundary points from the pillars) and then applying Dijkstra’s algorithm to determine the shortest valid path. Note that when checking an edge between two candidate points, you must verify that the entire straight-line segment satisfies the safety constraint. To that end, a ternary search along the segment is an acceptable method to approximate the minimum distance to each pillar.

inputFormat

The input begins with a line containing five floating-point numbers: x_start y_start x_target y_target R, where \(R\) is the radius of the stone.

The next line contains an integer \(N\) representing the number of stone pillars.

Each of the following \(N\) lines contains four floating-point numbers: x1 y1 x2 y2, describing a pillar as an axis‐aligned rectangle with its bottom‐left corner at \((x_1, y_1)\) and top‐right corner at \((x_2, y_2)\). You may assume that \(x_1 < x_2\) and \(y_1 < y_2\). All values are separated by spaces.

outputFormat

If a valid path exists, output a single floating-point number representing the minimum distance to push the stone, rounded to 6 decimal places. Otherwise, output -1.

sample

0 0 10 0 1
0

10.000000