bzoj4746: [Usaco2016 Dec]Lasers and Mirrors-布布扣-bubuko.com

　　　　　　　　　　　　　　　　bzoj4746: [Usaco2016 Dec]Lasers and Mirrors

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

Sample Output

首先因为镜子是可以有两种摆放方式或者不放以及一开始可以从各个方向射出所以不用记录射的方向只需记录当前是横的还是竖的以及直线所在的坐标

离散化后相邻的横纵坐标连长度为0的边如果在某个点有镜子则该点的横坐标和纵坐标之间连长度为1的边

最后跑最短路即可

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<queue>
 5 #include<algorithm>
 6 #include<map>
 7 #include<vector>
 8 #define rep(i,l,r) for(int i=l;i<=r;++i)
 9 const int N=502333;
10 using namespace std;
11 int n,x1,x2,y1,y2,cnt1,cnt2,num1[N],num2[N],dis[N],tot,head[N];
12 bool in[N];
13 struct zs{
14     int x,y;
15 }s[N];
16 struct node{
17     int to,next,w;
18 }e[N*2];
19 map<int,int>mp1,mp2;
20 inline void ins(int u,int v,int w){
21     e[++tot].to=v; e[tot].next=head[u]; head[u]=tot; e[tot].w=w;
22 }
23 inline void ins1(int x){
24     if(mp1.find(x)==mp1.end()) mp1[x]=1,num1[++cnt1]=x;
25 }
26 inline void ins2(int x){
27     if(mp2.find(x)==mp2.end()) mp2[x]=1,num2[++cnt2]=x;
28 }
29 inline int find1(int x){
30     int l=1,r=cnt1,mid;
31     while(l<=r){
32         mid=l+r>>1;
33         if(num1[mid]>x) r=mid-1;else if(num1[mid]==x)return mid;else l=mid+1;
34     }
35 }
36 inline int find2(int x){
37     int l=1,r=cnt2,mid;
38     while(l<=r){
39         mid=l+r>>1;
40         if(num2[mid]>x) r=mid-1;else if(num2[mid]==x)return mid;else l=mid+1;
41     }
42 }
43 int main(){
44     scanf("%d%d%d%d%d",&n,&x1,&y1,&x2,&y2);
45     ins1(x1); ins1(x2); ins2(y1); ins2(y2);
46     rep(i,1,n) scanf("%d%d",&s[i].x,&s[i].y),ins1(s[i].x),ins2(s[i].y);
47     sort(num1+1,num1+1+cnt1); sort(num2+1,num2+1+cnt2);
48     x1=find1(x1); x2=find1(x2); y1=find2(y1); y2=find2(y2);
49     rep(i,1,n) s[i].x=find1(s[i].x),s[i].y=find2(s[i].y);
50     
51 //    rep(i,1,cnt1-1) ins(i,i+1,0),ins(i+1,i,0);
52 //    rep(i,1,cnt2-1) ins(i+cnt1,i+1+cnt1,0),ins(i+1+cnt1,i+cnt1,0);
53     rep(i,1,n) ins(s[i].x,s[i].y+cnt1,1),ins(s[i].y+cnt1,s[i].x,1);
54     
55     in[x1]=in[y1+cnt1]=1;  queue<int>q; memset(dis,60,sizeof dis);
56     dis[x1]=dis[y1+cnt1]=0; q.push(x1); q.push(y1+cnt1);
57     while(!q.empty()){
58         int x=q.front(); q.pop(); in[x]=0;
59 //        printf("%d %d\n",(x>cnt1)?100+num2[x-cnt1]:num1[x],dis[x]);
60         for(int k=head[x];k;k=e[k].next) if(dis[x]+e[k].w<dis[e[k].to]){
61             dis[e[k].to]=dis[x]+e[k].w;
62             if(!in[e[k].to]){
63                 in[e[k].to]=1; q.push(e[k].to);
64             }
65         }
66     }
67     
68     printf("%d\n",min(dis[x2],dis[y2+cnt1]));
69 }

View Code

bzoj4746: [Usaco2016 Dec]Lasers and Mirrors

原文：http://www.cnblogs.com/Bloodline/p/6230962.html