Lasers and Mirrors#10564
For some reason, Farmer John's cows always seem to be putting on laser light shows.
For their latest show, the cows have acquired a large, powerful laser – so large, in fact, that they cannot easily move it from the location where it was delivered. They would like to somehow direct the laser's light to the barn on the other side of Farmer John's property.
Both the laser and the barn can be considered points in the 2D plane representing a map of FJ's farm. The cows plan to point the laser so that it emits a beam of light either horizontally or vertically (i.e., parallel to the - or -axis). They will then use a number of mirrors to redirect the beam toward the barn.
There are fence posts on the farm, each located at a distinct point in the 2D plane. The fence posts are also distinct from the laser and the barn. The cows may choose not to place a mirror on a particular fence post, in which case the laser beam simply passes over the post without changing direction.
If the cows do place a mirror on a fence post, they position it diagonally, like / or \, so that it redirects a horizontal beam of light vertically, or a vertical beam horizontally.
Please compute the minimum number of mirrors the cows need to use to redirect the laser beam to the barn.
The first line contains integers: n~(1 \le n \le 10^5), x_l, y_l, x_b, and y_b, where (x_l, y_l) is the location of the laser and (x_b, y_b) is the location of the barn. All coordinates are integers between and 10^9.
The next lines each contain two integers and , representing the location of a fence post. Both coordinates satisfy 0 \le x, y \le 10^9.
Print the minimum number of mirrors needed to direct the laser beam to the barn, or if it is impossible.
Example 1