Description
For some reason, Farmer John's cows always seem to be running laser light shows.For their latest sho
w, the cows have procured a large powerful laser -- so large, in fact, that they cannot seem to move
it easily from the location where it was delivered. They would like to somehow send the light from
the laser to the barn on the other side of FJ's property. Both the laser and the barn can be conside
red to be located at points in the 2D plane on a map of FJ's farm. The cows plan to point the laser
so that it sends a beam of light out either horizontally or vertically (i.e., aligned with the x or
y axes). They will then bounce this beam off a number of mirrors to direct it to the barn.On the far
m there are N fence posts (1≤N≤100,000) located at distinct 2D points (also distinct from the lase
r and the barn) at which the cows can mount mirrors. The cows can choose not to mount a mirror on a
fence post, in which case the laser would simply pass straight over the top of the post without chan
ging direction. If the cows do mount a mirror on a fence post, they align it diagonally like / or \
so that it will re-direct a horizontal beam of light in a vertical direction or vice versa.Please co
mpute the minimum possible number of mirrors the cows need to use in order to re-direct the laser to
the barn.
Input
The first line of input contains 5 space-separated integers: N,xL,yL,xB,yB
where (xL,yL) is the location of the laser and (xB,yB) is the location of the barn.
All coordinates are between 0 and 1,000,000,000
The next N lines each contain the xx and y locations of a fence post,
both integers in the range 0…1,000,000,000
Output
output the minimum number of mirrors needed to direct the laser to the barn,
or -1 if this is impossible to do.
Sample Input
4 0 0 7 2
3 2
0 2
1 6
3 0
1
/**************************************************************
Problem: 4746
User: ictsing
Language: C++
Result: Accepted
Time:712 ms
Memory:28632 kb
****************************************************************/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<map>
#include<vector>
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int N=502333;
using namespace std;
int n,x1,x2,y1,y2,cnt1,cnt2,num1[N],num2[N],dis[N],tot,head[N];
bool in[N];
struct zs{
int x,y;
}s[N];
struct node{
int to,next,w;
}e[N*2];
map<int,int>mp1,mp2;
inline void ins(int u,int v,int w){
e[++tot].to=v; e[tot].next=head[u]; head[u]=tot; e[tot].w=w;
//cout<<u<<" "<<v<<" "<<w<<endl;
}
inline void ins1(int x){
if(mp1.find(x)==mp1.end()) mp1[x]=1,num1[++cnt1]=x;
}
inline void ins2(int x){
if(mp2.find(x)==mp2.end()) mp2[x]=1,num2[++cnt2]=x;
}
inline int find1(int x){
int l=1,r=cnt1,mid;
while(l<=r){
mid=(l+r)>>1;
if(num1[mid]>x) r=mid-1;else if(num1[mid]==x)return mid;else l=mid+1;
}
return -1;
}
inline int find2(int x){
int l=1,r=cnt2,mid;
while(l<=r){
mid=(l+r)>>1;
if(num2[mid]>x) r=mid-1;else if(num2[mid]==x)return mid;else l=mid+1;
}
return -1;
}
int main(){
scanf("%d%d%d%d%d",&n,&x1,&y1,&x2,&y2);
ins1(x1); ins1(x2); ins2(y1); ins2(y2);
rep(i,1,n) scanf("%d%d",&s[i].x,&s[i].y),ins1(s[i].x),ins2(s[i].y);
sort(num1+1,num1+1+cnt1); sort(num2+1,num2+1+cnt2);
x1=find1(x1); x2=find1(x2); y1=find2(y1); y2=find2(y2);
rep(i,1,n)
{
s[i].x=find1(s[i].x),s[i].y=find2(s[i].y);
//cout<<s[i].x<<" "<<s[i].y<<endl;
}
// rep(i,1,cnt1-1) ins(i,i+1,0),ins(i+1,i,0);
// rep(i,1,cnt2-1) ins(i+cnt1,i+1+cnt1,0),ins(i+1+cnt1,i+cnt1,0);
rep(i,1,n)
{
ins(s[i].x,s[i].y+cnt1,1),ins(s[i].y+cnt1,s[i].x,1);
}
in[x1]=in[y1+cnt1]=1;
queue<int>q;
memset(dis,60,sizeof dis);
dis[x1]=dis[y1+cnt1]=0;
q.push(x1);
q.push(y1+cnt1);
while(!q.empty()){
int x=q.front(); q.pop(); in[x]=0;
//cout<<x<<endl;
// printf("%d %d\n",(x>cnt1)?100+num2[x-cnt1]:num1[x],dis[x]);
for(int k=head[x];k;k=e[k].next) if(dis[x]+e[k].w<dis[e[k].to]){
dis[e[k].to]=dis[x]+e[k].w;
//<<e[k].to<<" "<<dis[e[k].to]<<endl;
if(!in[e[k].to]){
in[e[k].to]=1; q.push(e[k].to);
}
}
}
//cout<<x2<<" "<<y2+cnt1<<" "<<dis[x2]<<" "<<dis[y2+cnt1]<<endl;
printf("%d\n",min(dis[x2],dis[y2+cnt1]));
}
评论