记录编号	605447	评测结果	AAAAAAAAAAA
题目名称	2578.激光	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	0.337 s
提交时间	2025-09-01 16:00:58	内存使用	7.43 MiB

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

const int N = 2e5+10;

int n,a,b,c,d;
int x[N],y[N],x2[N],y2[N],cnt1,cnt2;
int hd[N],to[N],nxt[N<<1],e[N<<1],idx,dis[N],vis[N];

void add(int x,int y,int z){
	to[++idx]=y;
	nxt[idx]=hd[x];
	e[idx]=z;
	hd[x]=idx;
}

int ax(int x){
	return lower_bound(x2+1,x2+cnt1+1,x)-x2;
}

int ay(int y){
	return lower_bound(y2+1,y2+cnt2+1,y)-y2;
}

void spfa(){
	queue<int> q;
	memset(dis,0x3f,sizeof(dis));
	q.push(ax(a));
	q.push(ay(b)+cnt1);
	dis[ax(a)]=dis[ay(b)+cnt1]=0;
	vis[ax(a)]=vis[ay(b)+cnt1]=1;
	while(q.size()){
		int x=q.front();q.pop();vis[x]=0;
		for(int i=hd[x];i;i=nxt[i]){
			int y=to[i],z=e[i];
			if(dis[y]>dis[x]+z){
				dis[y]=dis[x]+z;
				if(!vis[y]) q.push(y),vis[y]=1;
			}
		}
	}
}	

int main(){
	freopen("lasers.in","r",stdin);
	freopen("lasers.out","w",stdout);
	scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
	for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
	x[n+1]=a;y[n+1]=b;
	x[n+2]=c;y[n+2]=d;
	n+=2;
	memcpy(x2,x,sizeof x); 
	memcpy(y2,y,sizeof y);
	sort(x2+1,x2+1+n);
	sort(y2+1,y2+1+n);
	cnt1=unique(x2+1,x2+1+n)-x2-1;
	cnt2=unique(y2+1,y2+1+n)-y2-1;
	for(int i=1;i<=n;i++){
		add(ax(x[i]),ay(y[i])+cnt1,1);
		add(ay(y[i])+cnt1,ax(x[i]),1);
	}
	spfa();
	printf("%d",min(dis[ax(c)],dis[ay(d)+cnt1]));
}