记录编号	603141	评测结果	AAAAAAAAAAA
题目名称	2578.激光	最终得分	100
用户昵称	KKZH	是否通过	通过
代码语言	C++	运行时间	0.821 s
提交时间	2025-07-09 12:02:20	内存使用	22.29 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=2e6;
int n,sx,sy,ex,ey,cnt,cntx,cnty;
int head[N],dis[N],a[N][2],firx[N],firy[N];
map <int,int> mpx,mpy;
struct node1{
	int num,len;
	friend bool operator<(const node1 a,const node1 b){
		return a.len>b.len;
	}
};
struct node{
	int next,to,len;
}ed[N];
priority_queue <node1> q;
void add(int x,int y,int z){
	ed[++cnt].next=head[x];
	ed[cnt].to=y;
	ed[cnt].len=z;
	head[x]=cnt;
}
void dij(){
	while(!q.empty()){
        int d = q.top().len;
		int x=q.top().num;
		q.pop();
		if (d != dis[x]) continue;
		for(int i=head[x];i!=-1;i=ed[i].next){
			int y=ed[i].to,z=ed[i].len;
			if(dis[y]>dis[x]+z){
				dis[y]=dis[x]+z;
				q.push({y,dis[y]});
			}
		}
	}
}
int main(){
	freopen("lasers.in","r",stdin);
	freopen("lasers.out","w",stdout);
	memset(dis,0x3f,sizeof(dis));
	memset(head,-1,sizeof(head));
	cin>>n>>sx>>sy>>ex>>ey;
	int x,y;
	a[n+1][0]=sx;
	a[n+1][1]=sy;
	a[n+2][0]=ex;
	a[n+2][1]=ey;
	for(int i=1;i<=n;i++)
		cin>>a[i][0]>>a[i][1];
	n=n+2;
	for (int i = 1; i <= n; i++) {
        int x = a[i][0], y = a[i][1];
        if (mpx.find(x) == mpx.end()) {
            mpx[x] = ++cntx;
            firx[cntx] = i;
        } else {
            int j = firx[mpx[x]];
            add(i + n, j + n, 0);
            add(j + n, i + n, 0);
        }
        if (mpy.find(y) == mpy.end()) {
            mpy[y] = ++cnty;
            firy[cnty] = i;
        } else {
            int j = firy[mpy[y]];
            add(i, j, 0);
            add(j, i, 0);
        }
    }
	for(int i=1;i<=n;i++){
		add(i,i+n,1);
		add(i+n,i,1);
	}
	dis[n+n-1]=0;
	dis[n-1]=0;
	q.push({n-1,0});
	q.push({2*n-1,0});
	dij();
	int ans=min(dis[n],dis[2*n]);
	if(ans!=1061109567)
		cout<<ans;
	else cout<<-1;
	return 0;
}