前言

调了三天终于过了。
一道基于图论、初中平面几何基础的大模拟。
感谢

/www.desmos.com/calculator/emcwegdahq?lang=zh-CN)，其中所有点都可以拖动。绿点为浮标，数长度用。
彩蛋：不可以“不可以，总司令”。

题意

平面内给定起点 $S$、终点 $E$ 和 $n$ 个矩形。

• 走上下左右，只能在矩形边上转向，在平面的其他位置不能转向。
• 不能进入矩形内部。
• 可以以任意方向从起点出发。

求起点到终点的最短路径长度，或报告无解。

例如，本题样例中第一组数据如图所示。

思路

对于此题，单纯的 BFS 难以实现，并且在时间复杂度上也无法接受，考虑连点、建图跑最短路。

准备工作

先写图论部分，实现链式前向星存图、加边和一种单源最短路算法即可。本题无负权，可以采用还没死的 Dijkstra 算法。代码实现上把所有图论内容放在 namespace Graph 中。
为了后续建图的方便，我们令本题中所有的长方形都长这个样子：

其中 $A,B$ 为输入的两点，保证 $x_A<x_B,y_A>y_B$。这样 $C,D$ 可以由 $A,B$ 的坐标得到，即 $C(x_B,y_A),D(x_A,y_B)$。为了保证 $A,B$ 相对位置正确，输入时需要视情况交换 $A,B$ 的某个坐标。

之后，需要进行离散化，实现几何点 $(x,y)\to$ 图中结点 $u$ 的映射。以下代码中，一些函数和自定义类可以看名称理解其作用。

// Point 为自定义类，有 int x,y 两个值
// 离散化，id[A] 表示 (A.x, A.y) 在图中结点编号
int cnt=0;
map <Point,int> id;
// 返回 (A.x, A.y) 在图中结点编号，没有的建立新点
inline int PointID(const Point &A)
{
    if(id[A]!=0)
        return id[A];
    ++cnt;
    return id[A]=cnt;
}
// 两点是否连接过
map <pair<Point,Point>,bool> connected;
// 在几何图形中连接两点，边权为其几何距离
inline void Connect(const Point &A,const Point &B)
{
    if(A==B||connected[(pair<Point,Point>){A,B}]||connected[(pair<Point,Point>){B,A}])
        return;
    connected[(pair<Point,Point>){A,B}]=connected[(pair<Point,Point>){B,A}]=1;
    // Dist(A,B) 为 A,B 之间的距离
    Graph::AddEdge(PointID(A),PointID(B),Dist(A,B));
    Graph::AddEdge(PointID(B),PointID(A),Dist(A,B));
}

连边建图

假设有一点 $P(x_P,y_P)$，需要实现一个函数 $\mathbf{Make}(P)$ 建立点 $P$ 与给出的 $n$ 个矩形可能的连边。
因为不能进入矩形内部，所以只要找到 $P$ 分别向上、向下、向左、向右距离最小的 $4$ 个矩形并连接即可。找最小值时遍历所有矩形，时间复杂度 $O(n)$，可以接受。
为了处理同一矩形的同一条边上出现两个不同点 $T_1,T_2$ 却没有在图中连接 $T_1T_2$ 的情况，定义矩形 $\alpha$ 的边 $m$ 上连接过的点集为 $\mathrm{coord[\alpha]}[m]$。例如，一个矩形 $\alpha$ 的边 $BD$ 形如 $D\text-T_1\text-\text-T_2\text-B$，则 $\mathrm{coord[\alpha]}[BD]=\{D,T_1,T_2,B\}$，最后再依次连接 $DT_1,T_1T_2,T_2B$。代码中使用默认有序的 STL set 实现，省去排序过程。
下面给出的伪代码描述了找点 $P$ 向上、向下 $2$ 个矩形并连接的过程，其中 $\mathrm{Rectangles}$ 为输入的矩形集，$\square ACBD$ 定义为线段 $AC,CB,BD,AD$ 上点的并集，$A_{\alpha},B_{\alpha}$ 等定义为矩形 $\alpha$ 的对应顶点。
找到交点后将交点放进所在矩形边的 $\text{coord}$ 集合中，最后再枚举矩形的每条边依次连接即可。

$$\begin{aligned} \ & \underline{\mathbf{Make}(P)}\\ 1\ & \mathrm{min}x_1,\mathrm{min}x_2 \gets +\infty; \alpha_1,\alpha_2 \gets \emptyset\\ 2\ & \mathbf{for}\ \square ACBD \in \mathrm{Rectangles}:\\ 3\ & \quad \mathbf{if}\ l:x=x_P \cap \square ACBD \ne \emptyset:\\ 4\ & \qquad \mathbf{if}\ P\ \mathrm{is\ below}\ \square ACBD:\\ 5\ & \qquad\quad \mathrm{Point}\ T=(l:x=x_P \cap BD)\\ 6\ & \qquad\quad\mathbf{if}\ |PT| < \mathrm{min}x_1:\\ 7\ & \qquad\qquad \mathrm{min}x_1 \gets |PT|\\ 8\ & \qquad\qquad \alpha_1 \gets \square ACBD\\ 9\ & \qquad \mathbf{else\ if}\ P\ \mathrm{is\ above}\ \square ACBD:\\ 10\ & \qquad\quad \mathrm{Point}\ T=(l:x=x_P \cap AC)\\ 11\ & \qquad\quad\mathbf{if}\ |PT| < \mathrm{min}x_2:\\ 12\ & \qquad\qquad \mathrm{min}x_2 \gets |PT|\\ 13\ & \qquad\qquad \alpha_2 \gets \square ACBD\\ 14\ & \mathrm{Point}\ T_1=(l:x=x_P \cap B_{\alpha_1}D_{\alpha_1})\\ 15\ & \mathrm{Point}\ T_2=(l:x=x_P \cap A_{\alpha_2}C_{\alpha_2})\\ 16\ & \mathrm{Connect}\ PT_1,PT_2 \\ 17\ & \mathrm{Insert}\ T_1\ \mathrm{to\ coord[\alpha_1]}[BD] \\ 18\ & \mathrm{Insert}\ T_2\ \mathrm{to\ coord[\alpha_2]}[AC] \\ \end{aligned}$$

求交点坐标可以使用初中平面几何相关知识。对向左、向右两个方向上矩形的处理与上面相似，不再展示。

实现 $\mathbf{Make}(P)$ 函数后，对每个矩形 $ACBD$ 依次对其四个顶点进行 $\mathbf{Make}$ 操作。另外别忘了对 $S,E\ \mathbf{Make}$ 一下。

特殊情况

1. $n=0$，即没有矩形。
   这时可以节省时间，如果 $S,E$ 同在一条平行于坐标轴的直线上，那么答案就是 $|SE|$；否则无解。

2. $S=E$，即起点终点重合。
   为了减少可能的麻烦这里特判一下，显然答案为 $0$。

3. $n \ne 0,S \ne E$ 且 $S,E$ 在同一条平行于坐标轴的直线上。
   如果没有考虑这种情况或处理不当会 WA on #6。此时若 $S,E$ 之间没有矩形需要连接 $SE$。这个判断直接枚举即可，时间复杂度为 $O(n)$，为减小常数与最后处理 $\mathrm{coord}$ 的循环合并。
   另外，有一篇题解直接连接了 $SE$ 而不考虑它们之间是否有矩形，针对此有 hack 数据，具体见此贴。

最后建完图以 $S$ 为起点跑一波 Dijkstra，如果结果为 inf，报告无解；否则输出最短距离。

代码

上面思路中提到的问题仅仅是对平面几何关系最简洁直观的描述。真正的实现需要判断点坐标之间的关系，略为复杂，但是都在初中平面几何知识范围内，推出来也并不难。
完整代码见云剪贴板。总时间复杂度 $O(n^2)$，并且已经尽量合并循环、减小常数，对本题的 $3\text s$ 时限绰绰有余。
另外多测记得清空，建图要清彻底，就因为这个调了三天才过。

最后求过一下吧（可怜）。另外以现在的标准，这题现在还没有合规的题解。

引用自此，别手贱删了。

#include <bits/stdc++.h>
using namespace std;
#define maxn 2500005
#define endl '\n'
typedef long long ll;
namespace Basic
{
    inline int min(const int &x,const int &y){return x<y?x:y;}
    inline ll min(const ll &x,const ll &y){return x<y?x:y;}
    inline int max(const int &x,const int &y){return x>y?x:y;}
    inline ll max(const ll &x,const ll &y){return x>y?x:y;}
    inline void swap(int &x,int &y){x^=y^=x^=y;}
    inline void swap(ll &x,ll &y){x^=y^=x^=y;}
}
using namespace Basic;
// 图论部分
namespace Graph
{
    // 链式前向星存图
    int cnt=0,head[maxn];
    ll dis[maxn];
    #define llinf 0x7f7f7f7f7f7f7f7fll
    #define inf 0x7f7f7f7f
    bool vis[maxn];
    struct Edge
    {
        int to,next;
        ll w;
    } edge[maxn];
    // 添加一条单向边
    inline void AddEdge(const int &u,const int &v,const ll &w)
    {
        edge[++cnt].to=v;
        edge[cnt].w=w;
        edge[cnt].next=head[u];
        head[u]=cnt;
    }
    // Dijkstra 使用的结点
    struct DijNode
    {
        ll dis;
        int pos;
        inline bool operator <(const DijNode &x) const
        {
            return x.dis<dis;
        }
    };
    priority_queue <DijNode> q;
    // 最短路，结果存在 dis[i] 中
    inline void Dijkstra(const int &start)
    {
        dis[start]=0;
        q.push((DijNode){0,start});
        while(!q.empty())
        {
            DijNode t=q.top();
            q.pop();
            int x=t.pos,d=t.dis;
            if(vis[x])
                continue;
            vis[x]=1;
            for(int i=head[x];i;i=edge[i].next)
            {
                int y=edge[i].to;
                if(dis[y]>dis[x]+edge[i].w)
                {
                    dis[y]=dis[x]+edge[i].w;
                    if(!vis[y])
                        q.push((DijNode){dis[y],y});
                }
            }
        }
    }
}
namespace Problem
{
    int T,n;
    class Point
    {
        public:
            int x,y;
            Point()
            {
                x=y=0;
            }
            Point(const int &x_,const int &y_)
            {
                x=x_,y=y_;
            }
            inline void reset(const int &x_,const int &y_)
            {
                x=x_,y=y_;
            }
            inline friend istream& operator >>(istream& cin,Point &p)
            {
                return (cin >> p.x >> p.y);
            }
            inline friend ostream& operator <<(ostream& cout,const Point &p)
            {
                return (cout << "(" << p.x << "," << p.y << ")");
            }
            inline bool operator <(const Point &B) const
            {
                if(x != B.x)
                    return x<B.x;
                else
                    return y<B.y;
            }
    };
    inline bool operator ==(const Point &A,const Point &B)
    {
        return A.x==B.x && A.y==B.y;
    }
    // S,E 为起点、终点，A[i] 和 B[i] 为第 i 个长方形的端点
    Point S,E,A[1005],B[1005];
    // coord[id][i] 为第 id 个长方形第 i 条边上的点
    /* 边的编号
    A--0--C
    |     |
    3     1
    |     |
    D--2--B
    */
    set <Point> coord[1005][4];
    // 两点距离公式，本题无浮点数
    inline int Dist(const Point &A,const Point &B)
    {
        // 避免精度损失，特判(?)
        if(A.x==B.x)
            return abs(A.y-B.y);
        else if(A.y==B.y)
            return abs(A.x-B.x);
        return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
    }
    // 离散化，id[A] 表示 (A.x, A.y) 在图中结点编号
    int cnt=0;
    map <Point,int> id;
    // 返回 (A.x, A.y) 在图中结点编号，没有的建立新点
    inline int PointID(const Point &A)
    {
        if(id[A]!=0)
            return id[A];
        ++cnt;
        return id[A]=cnt;
    }
    // 两点是否连接过
    map <pair<Point,Point>,bool> connected;
    // 在几何图形中连接两点，边权为其几何距离
    inline void Connect(const Point &A,const Point &B)
    {
        if(A==B||connected[(pair<Point,Point>){A,B}]||connected[(pair<Point,Point>){B,A}])
            return;
        connected[(pair<Point,Point>){A,B}]=connected[(pair<Point,Point>){B,A}]=1;
        //printf("Connected (%d,%d) and (%d,%d), distance=%d\n",A.x,A.y,B.x,B.y,Dist(A,B));
        Graph::AddEdge(PointID(A),PointID(B),Dist(A,B));
        Graph::AddEdge(PointID(B),PointID(A),Dist(A,B));
    }
    // 连接点 Pt 的边，时间复杂度 O(n)
    inline void Make(const Point &Pt)
    {
        int mindx[3]={inf,inf,inf},mindy[3]={inf,inf,inf};
        int a1=inf,a2=inf,b1=inf,b2=inf;
        for(int i=1;i<=n;++i)
        {
            if(A[i].x <= Pt.x && Pt.x <= B[i].x)
            {
                if(Pt.y<B[i].y)
                {
                    const Point P(Pt.x,B[i].y);
                    if(Dist(Pt,P)<mindx[1])
                    {
                        mindx[1]=Dist(Pt,P);
                        a1=i;
                    }
                }
                else if(Pt.y>A[i].y)
                {
                    const Point P(Pt.x,A[i].y);
                    if(Dist(Pt,P)<mindx[2])
                    {
                        mindx[2]=Dist(Pt,P);
                        a2=i;
                    }
                }
            }
            if(B[i].y <= Pt.y && Pt.y <= A[i].y)
            {
                if(Pt.x<A[i].x)
                {
                    const Point P(A[i].x,Pt.y);
                    if(Dist(Pt,P)<mindy[1])
                    {
                        mindy[1]=Dist(Pt,P);
                        b1=i;
                    }
                }
                else if(Pt.x>B[i].x)
                {
                    const Point P(B[i].x,Pt.y);
                    if(Dist(Pt,P)<mindy[2])
                    {
                        mindy[2]=Dist(Pt,P);
                        b2=i;
                    }
                }
            }
        }
        Point P(0,0);
        if(a1!=inf)
        {
            P.reset(Pt.x,B[a1].y);
            Connect(P,Pt);
            coord[a1][2].insert(P);
        }
        if(a2!=inf)
        {
            P.reset(Pt.x,A[a2].y);
            Connect(P,Pt);
            coord[a2][0].insert(P);
        }
        if(b1!=inf)
        {
            P.reset(A[b1].x,Pt.y);
            Connect(P,Pt);
            coord[b1][3].insert(P);
        }
        if(b2!=inf)
        {
            P.reset(B[b2].x,Pt.y);
            Connect(P,Pt);
            coord[b2][1].insert(P);
        }
    }
    // 初始化
    inline void Init()
    {
        memset(Graph::dis,0x7f7f,sizeof(Graph::dis));
        memset(Graph::vis,0,sizeof(Graph::vis));
        Graph::cnt=cnt=0;
        while(!Graph::q.empty()) Graph::q.pop();
        memset(Graph::head,0,sizeof(Graph::head));
        memset(Graph::edge,0,sizeof(Graph::edge));
        memset(A,0,sizeof(A));
        memset(B,0,sizeof(B));
        for(int i=0;i<=n+1;++i)
            for(int p=0;p<4;++p)
                coord[i][p].clear();
        id.clear();
        connected.clear();
    }
}
using namespace Problem;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr),cout.tie(nullptr);
    cin >> T;
    while(T--)
    {
        cin >> S >> E >> n;
        Init();
        if(n==0)
        {
            if(S.x==E.x||S.y==E.y)
                cout << Dist(S,E) << endl;
            else
                cout << "No Path" << endl;
            continue;
        }
        if(S.x==E.x && S.y==E.y)
        {
            cout << 0 << endl;
            continue;
        }
        // 输入
        for(int i=1;i<=n;++i)
        {
            cin >> A[i] >> B[i];
            // 保证：A.x < B.x 且 A.y > B.y
            if(A[i].x > B[i].x)
                swap(A[i].x,B[i].x);
            if(A[i].y < B[i].y)
                swap(A[i].y,B[i].y);
            const Point Ci(B[i].x,A[i].y),Di(A[i].x,B[i].y);
            coord[i][0].insert(A[i]);
            coord[i][1].insert(Ci);
            coord[i][2].insert(B[i]);
            coord[i][3].insert(Di);
        }
        // 长方形之间的连边
        for(int i=1;i<=n;++i)
        {
            const Point Ci(B[i].x,A[i].y),Di(A[i].x,B[i].y);
            const Point pts[4]={A[i],Ci,B[i],Di};
            for(int p=0;p<4;++p)
                Make(pts[p]);
        }
        Make(S);
        Make(E);
        // 长方形边上的连边，顺便判断 S,E 是否可以直接连接(direct)
        bool direct=(S.x==E.x||S.y==E.y);
        for(int i=1;i<=n;++i)
        {
            const Point Ci(B[i].x,A[i].y),Di(A[i].x,B[i].y);
            const Point pts[4]={Ci,B[i],Di,A[i]};
            for(int p=0;p<4;++p)
            {
                coord[i][p].insert(pts[p]);
                auto last=coord[i][p].begin();
                // 这里的 auto：set<Point>::iterator
                for(auto it=coord[i][p].begin();it!=coord[i][p].end();++it)
                {
                    if(it!=coord[i][p].begin())
                        Connect(*last,*it);
                    last=it;
                }
            }
            if(S.x==E.x && min(S.y,E.y) <= B[i].y && A[i].y <= max(S.y,E.y) && A[i].x <= S.x && S.x <= B[i].x)
                direct=0;
            if(S.y==E.y && min(S.x,E.x) <= A[i].x && B[i].x <= max(S.x,E.x) && B[i].y <= S.y && S.y <= A[i].y)
                direct=0;
        }
        if(direct)
            Connect(S,E);
        // 跑最短路 Dij O(n^2)
        Graph::Dijkstra(PointID(S));
        if(Graph::dis[PointID(E)]==llinf)
            cout << "No Path" << endl;
        else
            cout << Graph::dis[PointID(E)] << endl;
    }
    return 0;
}