比赛 |
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;
}