比赛 2025暑期集训第5场图论专场 评测结果 AWWWWWWWWWA
题目名称 激光 最终得分 18
用户昵称 会挽弯弓满月 运行时间 0.273 s
代码语言 C++ 内存使用 5.22 MiB
提交时间 2025-07-09 10:31:13
显示代码纯文本
#include <bits/stdc++.h> 
using namespace std;
const int N=1e5+10;
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<48||c>57){
		if(c==45) f=-1;
		c=getchar();
	}
	while(c>=48&&c<=57){
		x=x*10+c-48;
		c=getchar();
	}
	return f*x;
}
int n,m;
int x[N],y[N];
int x2[N],y2[N];
int cx,cy,mx,my;
struct edge{
	int to,nxt;
}e[N<<1];
int h[N],tot;
void add(int u,int v){
	e[++tot].to=v;
	e[tot].nxt=h[u];
	h[u]=tot;
	return;
}
int cnt1,cnt2;
int aska(int s){
	return lower_bound(x2+1,x2+cnt1+1,s)-x2;
}
int askb(int s){
	return lower_bound(y2+1,y2+cnt2+1,s)-y2;
}
int dis[N];
bool vis[N];
queue<int> q;
void spfa(int x0,int y0){
	x0=aska(x0);
	y0=askb(y0);
	memset(dis,0x3f,sizeof(dis));
	dis[x0]=0;dis[y0]=0;
	vis[x0]=0;vis[y0]=0;
	q.push(x0);q.push(y0);
	int u,v;
	while(!q.empty()){
		u=q.front();q.pop();
		for(int i=h[u];i;i=e[i].nxt){
			v=e[i].to;vis[v]=0;
			if(dis[v]>dis[u]+1){
				dis[v]=dis[u]+1;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return;
}
int ans;
int main(){
	freopen("lasers.in","r",stdin);
	freopen("lasers.out","w",stdout);
	n=read();
	int xx,yy;
	m=n+2;
	cx=read();cy=read();mx=read();my=read();
	for(int i=1;i<=n;i++){
		xx=read();yy=read();
		x[i]=x2[i]=xx;y[i]=y2[i]=yy;
	}
	x[n+1]=x2[n+1]=cx;
	y[n+1]=y2[n+1]=cy;
	x[n+2]=x2[n+2]=mx;
	y[n+2]=y2[n+2]=my;
	sort(x2+1,x2+m+1);
	sort(y2+1,y2+m+1);
	cnt1=unique(x2+1,x2+m+1)-x2-1;
	cnt2=unique(y2+1,y2+m+1)-y2-1;
	for(int i=1;i<=m;i++){
		xx=aska(x[i]);
		yy=askb(y[i]);
		add(xx,yy);add(yy,xx);
	}
	spfa(cx,cy);
	mx=aska(mx);
	my=askb(my);
	ans=min(dis[mx],dis[my]);
	printf("%d",ans);
	return 0;
}