(Analysis by Nick Wu)

In this problem, we want to shoot a laser from a source point to a destination point. The laser starts out being horizontal or vertical, and diagonal mirrors can be inserted in certain locations to change the orientation of the laser. We want to insert the minimum number of lasers needed to reach the destination.

We start by making an observation about any optimal path of the laser - given any horizontal or vertical line, the laser will only cover at most one contiguous interval of the line. If the laser covers two disjoint intervals, we can "skip" part of the path that goes off of that line and get a more optimal path.

Therefore, there are at most $2N+2$ lines that the laser can travel on - $N+1$ horizontal ones and $N+1$ vertical ones each corresponding to the initial point and the $N$ points where we can place mirrors.

We can then model this problem as a shortest path problem. We want to get to either a horizontal or vertical line that goes through the destination point, and we start on a horizontal or vertical line that goes through the start point. We can transfer between two lines if and only if their intersection point is one of the $N$ points given to us, and we want to minimize the number of transfers we do.

import java.io.*;
import java.util.*;
public class lasers {
public static void main(String[] args) throws IOException {
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("lasers.out")));
int n = Integer.parseInt(st.nextToken());
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
Map<Line, Integer> dist = new HashMap<Line, Integer>();
dist.put(new Line(y1, true), 0);
dist.put(new Line(x1, false), 0);
Map<Integer, ArrayList<Integer>> xtoY = new HashMap<Integer, ArrayList<Integer>>();
Map<Integer, ArrayList<Integer>> ytoX = new HashMap<Integer, ArrayList<Integer>>();
for(int i = 0; i < n; i++) {
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
if(!xtoY.containsKey(x)) {
xtoY.put(x, new ArrayList<Integer>());
}
if(!ytoX.containsKey(y)) {
ytoX.put(y, new ArrayList<Integer>());
}
}
int ret = -1;
while(!q.isEmpty()) {
Line curr = q.removeFirst();
if(curr.horizontal && curr.val == y2) {
ret = dist.get(curr);
break;
}
if(!curr.horizontal && curr.val == x2) {
ret = dist.get(curr);
break;
}
Map<Integer, ArrayList<Integer>> source = curr.horizontal ? ytoX : xtoY;
if(source.containsKey(curr.val)) {
for(int dest: source.get(curr.val)) {
Line nextLine = new Line(dest, !curr.horizontal);
if(!dist.containsKey(nextLine)) {
dist.put(nextLine, dist.get(curr) + 1);
}
}
}
}
pw.println(ret);
pw.close();
}

static class Line {
public int val;
public boolean horizontal;
public Line(int val, boolean horizontal) {
super();
this.val = val;
this.horizontal = horizontal;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + (horizontal ? 1231 : 1237);
result = prime * result + val;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Line other = (Line) obj;
if (horizontal != other.horizontal)
return false;
if (val != other.val)
return false;
return true;
}

}
}