405010: GYM101736 J Journey
Description
The little green Cactus is on his daily run through the cactus desert. As usual, he is coding problem J as he runs. However, he forgot his charger today, and his computer is running out of battery. Now Cactus must run from point A (his current location) to point B (the location of his charger).
There are n oddly rectangular cacti in the desert, and Cactus cannot run through these cacti. No two cacti overlap, but they may touch at a point or on a line segment. Cactus cannot run through the points where two cacti touch. Find the minimum distance that Cactus must run to get from A to B.
InputThe first line of input contains a single integer n (0 ≤ n ≤ 100), the number of cacti.
Each of the next n lines contains four space-separated integers ai, bi, xi, and yi ( - 106 ≤ ai < xi ≤ 106; - 106 ≤ bi < yi ≤ 106), describing the bottom left and the top right corners of the cactus (on the Cartesian plane).
The last line of input contains four space-separated integers Ax, Ay, Bx, By ( - 106 ≤ Ax, Ay, Bx, By ≤ 106), describing point A and point B. It is guaranteed that A and B do not lie in the interior or on the boundary of a cactus.
OutputPrint the minimum distance Cactus must run, or - 1 if he cannot run from A to B. The answer will be considered correct if the relative or absolute error is at most 10 - 6.
ExampleInput3Output
0 0 1 1
0 1 1 2
1 -1 5 0
0 -1 2 1
5.4142135624