Description

原题面

在平面上有 $n$ 个平行于坐标轴的矩形障碍物, 现需要将一个半径为 $r$ 的圆从 $A$ 点移动到 $B$ 点. 请计算最短路. $(n \leq 30)$

Input Format

本题是多组数据，第一行一个整数 $T(T\leq 30)$ 表示数据组数，接下来依次描述每一组数据，每组数据第一行两个整数$r,n(1\leq r\leq 100,0\leq n\leq 30)$如上所述。第二行包含4个整数$x_A,y_A,x_B,y_B$，$(x_A,y_A)$ 表示起点 $A$ 坐标，$(x_B,y_B)$ 表示终点 $B$ 坐标。接下来n行每行4个整数 $x_1,y_1,x_2,y_2$，$(x_1,y_1)$ 表示矩形障碍物左下角坐标，$(x_2,y_2)$ 表示矩形障碍物右上角坐标。 矩形不会互相覆盖或接触，起点的坐标是合法的，即一开始不会与任何矩形相交（但是可能和某些矩形相切）

Output Format

每组数据输出一行，一个实数，输出保留6位小数，即从 $A$ 到 $B$ 不穿过矩形的最短路，如果不存在最短路请输出no solution。

1
1 3
2 7 7 1
3 2 6 4
7 5 9 8
1 8 5 9
2 4
0 0 5 6
8 3 10 6
5 9 9 10
1 4 2 8
3 1 5 3
1 2
0 5 10 5
2 2 4 5
6 5 8 8

10.570796.
no solution
11.652892