#P3036. [USACO16DEC] Lasers and Mirrors G

[USACO16DEC] Lasers and Mirrors G

题目描述

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.

对于他们的最新展会,奶牛已经购买了一个大功率的激光器 - 这么大,事实上,他们似乎不能轻易地从它交付的位置移动。他们想以某种方式将激光的光发送到FJ物业另一侧的谷仓。激光器和谷仓都可以被认为位于FJ农场的地图上的2D平面中的点上。牛计划指挥激光器,使得它发出水平或竖直(即,与x或y轴平行)的光束。他们会将这个光束从一些镜子反射回去,直接到谷仓。

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.

在农场上有NN个栅栏(1N100,0001 \leq N \leq 100,000),位于不同的二维点(也不同于激光和谷仓),牛可以安装镜子。可以选择不在护栏柱上安装镜子,在这种情况下,激光器将简单地直接通过柱子的顶部而不改变方向。如果母牛确实在栅栏柱上安装了一个镜子,它们会像/或\对齐,使得它将在垂直方向上重定向光束,反之亦然。

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.

第一行输入包含5个空格分隔的整数:N,xL,yL,xB,yBN, x_L, y_L, x_B, y_B,其中(xL,yL)(x_L, y_L)是激光器的位置,(xB,yB)(x_B, y_B)是谷仓的位置。 所有坐标都在001,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.

接下来的N行每行包含围栏柱的xxyy位置,两个整数在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

提示

感谢@huzhaoyang 提供翻译