记录编号	603398	评测结果	AAAAAAAAAAA
题目名称	2578.激光	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	0.325 s
提交时间	2025-07-11 16:15:44	内存使用	6.11 MiB

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

const int MAXN = 100005;
vector<int> xs, ys;
struct node{
    int s, p, d;
};
bool vis[MAXN];
queue<node> q;
int px[MAXN], py[MAXN];
int n, sx, sy, ex, ey;

int lsh_x(int x){
    return lower_bound(xs.begin(), xs.end(), x) - xs.begin();
}

int lsh_y(int y){
    return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}

int main(){
	freopen("lasers.in","r",stdin);
	freopen("lasers.out","w",stdout);
    cin.tie(0) -> ios::sync_with_stdio(0);

    cin >> n >> sx >> sy >> ex >> ey;

    xs.push_back(sx); xs.push_back(ex);
    ys.push_back(sy); ys.push_back(ey);

    for(int i = 0;i < n;i ++){
        cin >> px[i] >> py[i];
        xs.push_back(px[i]); ys.push_back(py[i]);
    }

    sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end());
    sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());

    int sxid = lsh_x(sx), syid = lsh_y(sy);
    int exid = lsh_x(ex), eyid = lsh_y(ey);

    vector<vector<pair<int, int> > > Ex(xs.size());
    vector<vector<pair<int, int> > > Ey(ys.size());

    for(int i = 0;i < n;i ++){
        int x = px[i], y = py[i];
        int xid = lsh_x(x), yid = lsh_y(y);
        Ex[xid].emplace_back(i, yid);
        Ey[yid].emplace_back(i, xid);
    }

    q.push((node){0, sxid, 1});
    q.push((node){0, syid, 0});

    while(!q.empty()){
    	auto x = q.front();
    	int s = x.s, p = x.p, d = x.d;
        q.pop();
        if((d && (p == exid)) || (!d && (p == eyid))){
            cout << s << '\n';
            return 0;
        }
        if(d){
            for(auto x : Ex[p]){
            	int id = x.first, y_id = x.second;
                if(!vis[id]){
                    q.push({s + 1, y_id, 0});
                    vis[id] = 1;
                }
            }
            Ex[p].clear();
        }
		else{
            for(auto y : Ey[p]){
            	int id = y.first, x_id = y.second;
                if(!vis[id]){
                    q.push({s + 1, x_id, 1});
                    vis[id] = true;
                }
            }
            Ey[p].clear();
        }
    }
    cout << -1 << '\n';
    return 0;
}