A1020.Lasers and Mirrors--Gold

提高+/省选-

USACO

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

For some reason, Farmer John's cows always seem to be running laser light
shows.
For their latest show, 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 considered 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 farm there are NN fence posts (1N100,0001 \leq N \leq 100,000) located at
distinct 2D points (also distinct from the laser 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 changing 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 compute the minimum possible number of mirrors the cows need to use in
order to re-direct the laser to the barn.

输入格式

The first line of input contains 5 space-separated integers: N,xL,yL,xB,yBN, x_L, y_L, x_B, y_B, where (xL,yL)(x_L, y_L) is the location of the laser and (xB,yB)(x_B, y_B) is
the location of the barn. All coordinates are between 00 and 1,000,000,0001,000,000,000.
The next NN lines each contain the xx and yy locations of a fence post,
both integers in the range 01,000,000,0000 \ldots 1,000,000,000.

输出格式

Please output the minimum number of mirrors needed to direct the laser to the
barn, or -1 if this is impossible to do.

输入输出样例

  • 输入#1

    4 0 0 7 2
    3 2
    0 2
    1 6
    3 0
    

    输出#1

    1
    
首页