Ice Walls

Have you ever played DOTA? If so, you may know the hero, Invoker. As one of the few intelligence carries, Invoker has 10 powerful abilities. One of them is the Ice Wall: Invoker generates a wall of solid ice directly in front of him, and the bitter cold emanating from it greatly slows nearby enemies and deals damage each second.

Now consider the map as a plane. You are now at point s, and want to move to point t. But Invoker has placed N ice walls on the map. Your moving speed is 1 per second, but you need k seconds to pass an ice wall. Time is precious, you must get to point t as quickly as possible. What's the minimum time you need?

For convenience, you can assume that all ice walls are segments (no width) either parallel to X-axis or to Y-axis. Segments are strictly disjoint (have no common point). Point s and t are not on any segment (have no common point).

You will not be slowed when pass the end point of a segment or walk along a segment.

The input begins with an integer T, indicating the number of test cases. For each case, the first line is two integers N and k (1 <= N <= 500, 0 <= k <= 10^8), indicating the number of segments and the time needed to pass an ice wall. Next N lines, each have four integers x1, y1, x2, y2, indicating two end points of a segment, (x1, y1) and (x2, y2). Next line has two integers xs and ys, representing the coordinates of starting point s. The last line also has two integers xt and yt, representing the coordinates of target point t. For every point, |x| and |y| <= $10^8$.

For each case, output one line containing the minimum time in second needed to get to t from s. The answer should be given within an absolute or relative error of $10^{-6}$.

3
1 1
1 0 1 2
0 0
2 0
1 1
1 -2 1 2
0 0
2 0
1 3
1 -2 1 2
0 0
2 0

2.000000
3.000000
4.472136

SYSU

2016 Multi-University Training Contest 7