题解

只允许水平或垂直击球，遇到矩形障碍会在边界停下。最短击球次数等价于在“可见点”之间做无权最短路：方向一直走直到碰到障碍或目标，中途不会停下。最优路径只需在矩形顶点（加起点、终点）处转弯，因为落在边上任意一点再走，与落在端点击球次数相同。

建图思路：把所有节点设为起点、终点和每个矩形四个顶点；当两节点在同一条水平或垂直直线上且中间不穿过障碍内部时，连一条长度为 $1$ 的边。最后在此图上 BFS 求最短路。

判定“线段是否被阻挡”：按坐标扫描维护当前 $x$（或 $y$）下穿过的矩形集合。

• 垂直方向：事件按 $x$ 排序；矩形 $[A,B]$ 在 $(A,B)$ 内有效。对每个出现的 $x$，取该 $x$ 上的所有节点按 $y$ 排序，相邻节点之间若当前活动矩形集中没有与其开放区间相交的 $[C,D]$，则可以互连。
• 水平方向同理，交换 $x$/$y$。

活动集合只需维护一组互不相交的区间，查询某开放区间 $(l,r)$ 是否有交即可用 set 的相邻元素完成，单次 $\\mathcal{O}(\\log N)$。总体建边 $\\mathcal{O}((N+M)\\log N)$，节点数 $M\\approx 4N+2$，最后 BFS 为 $\\mathcal{O}(N+M)$。

#include <bits/stdc++.h>
using namespace std;

struct Rect{ long long a,b,c,d; };
struct Node{ long long x,y; };

struct IntervalSet{
    set<pair<long long,long long>> s; // disjoint [l,r]
    void insert(pair<long long,long long> it){ s.insert(it); }
    void erase(pair<long long,long long> it){ s.erase(it); }
    bool intersects(long long l,long long r) const{
        auto it=s.lower_bound({l, (long long)-4e18});
        if(it!=s.end() && it->first<=r && it->second>=l) return true;
        if(it!=s.begin()){ --it; if(it->second>=l) return true; }
        return false;
    }
};

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    long long S,T,U,V; int N; if(!(cin>>S>>T>>U>>V)) return 0; cin>>N;
    vector<Rect> R(N); for(auto &r:R) cin>>r.a>>r.b>>r.c>>r.d;

    vector<Node> nodes; nodes.push_back({S,T}); nodes.push_back({U,V});
    for(auto &r:R){ nodes.push_back({r.a,r.c}); nodes.push_back({r.a,r.d}); nodes.push_back({r.b,r.c}); nodes.push_back({r.b,r.d}); }
    int M=nodes.size();
    vector<vector<pair<int,int>>> g(M);

    // vertical visibility
    {
        vector<long long> xs; xs.reserve(M); for(auto &n:nodes) xs.push_back(n.x);
        sort(xs.begin(),xs.end()); xs.erase(unique(xs.begin(),xs.end()), xs.end());
        vector<vector<int>> onX(xs.size());
        for(int i=0;i<M;++i){ int id=lower_bound(xs.begin(),xs.end(),nodes[i].x)-xs.begin(); onX[id].push_back(i); }
        vector<tuple<long long,int,pair<long long,long long>>> ev;
        for(auto &r:R){ ev.push_back({r.b,0,{r.c,r.d}}); ev.push_back({r.a,2,{r.c,r.d}}); }
        for(auto x:xs) ev.push_back({x,1,{0,0}});
        sort(ev.begin(),ev.end(),[](auto &A,auto &B){
            if(get<0>(A)!=get<0>(B)) return get<0>(A)<get<0>(B);
            return get<1>(A)<get<1>(B); // exit, query, enter
        });
        IntervalSet active;
        for(auto &e:ev){
            long long x=get<0>(e); int tp=get<1>(e); auto seg=get<2>(e);
            if(tp==0) active.erase(seg);
            else if(tp==2) active.insert(seg);
            else{
                int id=lower_bound(xs.begin(),xs.end(),x)-xs.begin();
                auto vec=onX[id];
                sort(vec.begin(),vec.end(),[&](int a,int b){ return nodes[a].y<nodes[b].y; });
                for(size_t k=1;k<vec.size();++k){
                    int u=vec[k-1], v=vec[k];
                    if(!active.intersects(nodes[u].y, nodes[v].y)){
                        g[u].push_back({v,1}); g[v].push_back({u,1});
                    }
                }
            }
        }
    }
    // horizontal visibility
    {
        vector<long long> ys; ys.reserve(M); for(auto &n:nodes) ys.push_back(n.y);
        sort(ys.begin(),ys.end()); ys.erase(unique(ys.begin(),ys.end()), ys.end());
        vector<vector<int>> onY(ys.size());
        for(int i=0;i<M;++i){ int id=lower_bound(ys.begin(),ys.end(),nodes[i].y)-ys.begin(); onY[id].push_back(i); }
        vector<tuple<long long,int,pair<long long,long long>>> ev;
        for(auto &r:R){ ev.push_back({r.d,0,{r.a,r.b}}); ev.push_back({r.c,2,{r.a,r.b}}); }
        for(auto y:ys) ev.push_back({y,1,{0,0}});
        sort(ev.begin(),ev.end(),[](auto &A,auto &B){
            if(get<0>(A)!=get<0>(B)) return get<0>(A)<get<0>(B);
            return get<1>(A)<get<1>(B);
        });
        IntervalSet active;
        for(auto &e:ev){
            long long y=get<0>(e); int tp=get<1>(e); auto seg=get<2>(e);
            if(tp==0) active.erase(seg);
            else if(tp==2) active.insert(seg);
            else{
                int id=lower_bound(ys.begin(),ys.end(),y)-ys.begin();
                auto vec=onY[id];
                sort(vec.begin(),vec.end(),[&](int a,int b){ return nodes[a].x<nodes[b].x; });
                for(size_t k=1;k<vec.size();++k){
                    int u=vec[k-1], v=vec[k];
                    if(!active.intersects(nodes[u].x, nodes[v].x)){
                        g[u].push_back({v,1}); g[v].push_back({u,1});
                    }
                }
            }
        }
    }

    const int INF=1e9;
    vector<int> dist(M, INF); queue<int> q; dist[0]=0; q.push(0);
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(auto [v,w]:g[u]) if(dist[v]>dist[u]+w){ dist[v]=dist[u]+w; q.push(v); }
    }
    cout<<dist[1]<<'\n';
    return 0;
}