题目

给出一个含有若干个不相交矩形的平面直角坐标系，以及起点和终点。
从起点到终点的路途中，不能经过矩形，但是可以在矩形边经过。
求最短的曼哈顿距离。
$n\leq 2e5$

---

正解

比赛时认为是欧几里得距离，所以不存在思考……

先说DYP的做法：
对于一个点，找到上下左右第一个碰到的边界，然后可以形成一个矩形。这个点可以曼哈顿最短距离到达矩形内任意点。
然后每个顶点以及起点终点向周围连边，连的是最近碰到的每个边界的两个端点。
然后跑最短路。

在说奇妙的正解：
由于这题的矩形都不相交，于是有些很神奇的性质。
以下建议感性理解，不解释
首先，横坐标和纵坐标至少有一个是单调的。
假设横坐标单调，如何判断？
钦定起点在终点左边，假如起点在终点上面，从起点开始不停往下走，遇到障碍就往右。
一直走到终点所在的那一列，如果这时候纵坐标小于终点，那么就不单调。

接下来考虑如何计算答案。
假如起点在终点左边。从起点开始往右扫，遇到障碍就分两路到障碍的两边，并且将横坐标移到障碍这里。（如果没有遇到障碍，先暂时保持着横坐标不变，具体原因自己去玩）
一直这么做下去，直到计算过两列之间的所有障碍。
剩下的距离就是最短的曼哈顿距离。

无法用精准的语言来说明它的正确性，但它就是很对……
这个东西随便用set维护就可以了。

---

代码

具体细节在此

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <set>
#define N 200010
int n;
struct DOT{int x,y;void swap(){std::swap(x,y);}
} S,T;
struct Sqr{DOT p,q;
} z[N];
int ans=INT_MAX;
struct Segment{int x,l,r;
} seg[N*2];
int m;
bool cmp1(Segment a,Segment b){return a.x>b.x;}
bool cmp0(Segment a,Segment b){return a.x<b.x;}
struct Status{int y;mutable int x,s;
};
bool operator<(Status a,Status b){return a.y<b.y;}
multiset<Status> s;
bool judge(){if (S.x>T.x)swap(S,T);if (S.y>T.y){m=0;for (int i=1;i<=n;++i)if (S.y>z[i].q.y && z[i].q.y>T.y)seg[++m]={z[i].q.y,z[i].p.x,z[i].q.x};sort(seg+1,seg+m+1,cmp1);}else{m=0;for (int i=1;i<=n;++i)if (S.y<z[i].p.y && z[i].p.y<T.y)seg[++m]={z[i].p.y,z[i].p.x,z[i].q.x};sort(seg+1,seg+m+1,cmp0);}int x=S.x;for (int i=1;i<=m;++i)if (seg[i].l<x && x<seg[i].r)x=seg[i].r;return x<=T.x;
}
void calc(){ if (S.x>T.x)swap(S,T);s.clear();m=0;for (int i=1;i<=n;++i)if (S.x<z[i].p.x && z[i].p.x<T.x)seg[++m]={z[i].p.x,z[i].p.y,z[i].q.y};sort(seg+1,seg+m+1,cmp0);s.insert({S.y,S.x,0});for (int i=1;i<=m;++i){int x=seg[i].x,l=seg[i].l,r=seg[i].r;set<Status>::iterator p=s.lower_bound({l}),u,v;bool appear=0;for (auto q=p;p!=s.end() && l<p->y && p->y<r;q=p,++p,s.erase(q)){if (appear==0){appear=1;//s.insert() return pair<...,bool>u=s.insert((Status){r,x,p->s+(x-p->x)+abs(p->y-r)})/*.first*/;v=s.insert((Status){l,x,p->s+(x-p->x)+abs(p->y-l)})/*.first*/;}else{u->s=min(u->s,p->s+(x-p->x)+abs(p->y-r));v->s=min(v->s,p->s+(x-p->x)+abs(p->y-l));}}}for (auto p=s.begin();p!=s.end();++p)ans=min(ans,p->s+(T.x-p->x)+abs(p->y-T.y));
}
int main(){
//	freopen("in.txt","r",stdin);freopen("travel.in","r",stdin);freopen("travel.out","w",stdout);scanf("%d%d%d%d%d",&n,&S.x,&S.y,&T.x,&T.y);for (int i=1;i<=n;++i)scanf("%d%d%d%d",&z[i].p.x,&z[i].p.y,&z[i].q.x,&z[i].q.y);if (judge())calc();S.swap(),T.swap();for (int i=1;i<=n;++i)z[i].p.swap(),z[i].q.swap();if (judge())calc();printf("%d\n",ans);return 0;
}

---

总结

还是不要总想着数据结构……
有些问题性质很优美的……