POJ 3151 - Driving Directions

题目描述

与人们通常的想法不同，外星飞碟并不能在地球上空任意飞行。它们的降落和起飞会消耗大量能量，因此执行地球任务时，它们会精心规划：先在某个地点降落，然后贴近地面悬停执行任务，最后再起飞。

在人类文明早期，这很容易，因为飞碟可以悬停在树木和建筑物之上，从一个任务点到另一个任务点的最短路径通常就是一条直线。然而，现代城市中出现了许多非常高的摩天大楼，飞碟无法从它们上方飞过，于是在现代城市中导航就变得相当复杂。

你受雇于一名外星间谍，需要编写一个程序，最终用于为飞碟提供城市中的“行驶路线”。作为第一个任务，你需要编写程序，计算飞碟从一个点到另一个点所需经过的最短距离。这个程序将被外星人用于估计任务所需的能量。

本题做如下简化：

1. 飞碟可以悬停在大多数建筑上方，因此只需要考虑摩天大楼；
2. 问题是二维的，可以从上方俯视，所有物体都位于 $OXY$ 笛卡尔平面上；
3. 飞碟被表示为一个半径为 $r$ 的圆；
4. 每座摩天大楼被表示为一个边平行于坐标轴的矩形。

飞碟的位置定义为其圆心的位置，飞碟经过的路径长度定义为其圆心轨迹的长度。

在执行任务过程中，飞碟可以接触摩天大楼，但不能与摩天大楼的内部相交。

给定飞碟半径、起点、终点以及若干矩形摩天大楼，求飞碟从起点到终点的最短可行路径长度。如果无法到达终点，输出 no solution。

图示说明

• 第一幅图中，半径 $r=1$ 的飞碟需要从点 $A$ 到点 $B$。若没有障碍，直线最短；但被第一座摩天大楼阻挡。绕过第一座楼右上角虽然局部较短，但第二座楼太近，无法通过，因此最短路径需要绕过第一座楼左下角，总长度为 10.570796。
• 第二幅图中，半径 $r=2$ 的飞碟无法从 $A$ 到达 $B$，因为摩天大楼之间距离太近，飞碟无法通过。
• 第三幅图中，半径 $r=1$ 的飞碟需要以类似“回转滑雪”的方式绕过两座摩天大楼，最短路径长度为 11.652892。

输入格式

输入仅包含一组数据。

第一行包含两个整数 $r,n$，分别表示飞碟半径和摩天大楼数量。

第二行包含四个整数：

$$x_A,\ y_A,\ x_B,\ y_B$$

表示飞碟任务的起点 $(x_A,y_A)$ 和终点 $(x_B,y_B)$。

接下来 $n$ 行，每行描述一座摩天大楼，包含四个整数：

$$x_1,\ y_1,\ x_2,\ y_2$$

表示对应矩形的两个对角点坐标，满足：

$$x_1 < x_2,\qquad y_1 < y_2$$

矩形边均与坐标轴平行。

输出格式

如果飞碟无法从起点到达终点，输出：

no solution

否则输出一个实数，表示飞碟从起点到终点需要经过的最短距离。

答案至少需要精确到小数点后 $6$ 位。

数据范围

$$1 \le r \le 100$$ $$0 \le n \le 30$$ $$-1000 \le x_A,y_A,x_B,y_B \le 1000$$ $$-1000 \le x_1,y_1,x_2,y_2 \le 1000$$ $$x_1 < x_2,\qquad y_1 < y_2$$

任意两座摩天大楼互不相交，也不接触。

起点和终点都是飞碟的合法位置，即飞碟在这些位置时不会与任何摩天大楼相交，但可以接触某些摩天大楼。

样例输入 #1

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

样例输出 #1

10.570796

样例输入 #2

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

样例输出 #2

no solution

样例输入 #3

1 2
0 5 10 5
2 2 4 5
6 5 8 8

样例输出 #3

11.652892