In League of Legends, Blast Cone is a type of plant with explosive fruit. Their explosive properties are powerful enough to fling a humanoid several meters away.
Cryin used Blast Cone to speed up the movement of him and his teammates. Suppose your character is in the Summoner's Rift now. For simplicity,
- The Summoner's Rift can be regarded as an infinite 2-dimensional plane, and your character is a point ignoring the radius;
- All the barriers are rectangles whose sides are parallel to coordinate axes, you can not go strictly inside the barriers, which means the borders are accessible;
- To use a blast cone, you can go to the location of it, destroy it, and then you can control yourself to jump to any position except those in the barrier within the distance of $$$R$$$. You can assume that the process is instantaneous, that is, it won't take any time.
There are $$$n$$$ rectangle barriers and $$$m$$$ Blast Cones. Now you start from the starting point $$$(x_s,\ y_s)$$$ and you want to reach the end point $$$(x_t,\ y_t)$$$. Your moving speed is $$$1$$$ unit length per second. Can you calculate the minimum time cost from starting point to end point?
The first line contains three integers $$$n, m, R~(0\le n,\ m\le 40,\ 1\le R\le 10^6)$$$, denoting the number of rectangle barriers, the number of Blast Cones and the jump radius, respectively.
In the following $$$n$$$ lines, the $$$i$$$-th line contains four integers $$$x^b_{i,1},\ y^b_{i,1},\ x^b_{i,2},\ y^b_{i,2}$$$ ($$$-10^6\le x^b_{i,1},\ y^b_{i,1},\ x^b_{i,2},\ y^b_{i,2}\le 10^6,\ \ x^b_{i,1} \lt x^b_{i,2},\ \ y^b_{i,1} \lt y^b_{i,2}$$$), which denotes the $$$i$$$-th barrier's bottom left corner is $$$(x^b_{i,1},\ y^b_{i,1})$$$ and its upper right corner is $$$(x^b_{i,2},\ y^b_{i,2})$$$.
In the following $$$m$$$ lines, the $$$i$$$-th line contains two integers $$$x^c_{i},\ y^c_{i}$$$ ($$$-10^6 \le x^c_i,\ y^c_i\le 10^6$$$), which denotes the $$$i$$$-th Blast Cone is at $$$(x^c_i,\ y^c_i)$$$.
The last line contains four integers $$$x_s,\ y_s,\ x_t,\ y_t$$$ ($$$-10^6 \le x_s,\ y_s,\ x_t,\ y_t\le 10^6$$$), denoting the starting point $$$s$$$ and the end point $$$t$$$.
It is guaranteed that:
- Any two barriers don't share a point, including the borderlines and the corners.
- The positions of Blast Cones, the starting point $$$s$$$ and the end point $$$t$$$ are pairwise distinct, and are all strictly outside the barriers.
Output a decimal real number in a single line, denoting the minimum time cost from starting point to end point. Your answer will be judged as correct, if the relative or absolute error between your answer and jury's answer is less than or equal to $$$10^{-6}$$$.
It's guaranteed that there are valid solutions by the given condition.
To print a fixed decimal number for some digits after the decimal point, say, $$$9$$$ digits, you can use
- printf("%.9lf\n", ans) or printf("%.9Lf\n", ans) in C-style output;
- cout << fixed << setprecision(9) << ans << endl in C++;
- print("%.9f" % ans) in Python.
1 2 2 0 2 7 4 -3 3 8 2 1 1 6 6
9.543203767
The figure of the sample input is as follows:
The answer is $$$\sqrt{7^2+1^2} + \sqrt{2^2+4^2} - 2 \approx 9.543203767$$$.
