Lasers and Mirrors

题目描述

出于某些原因，Farmer John 的奶牛们似乎总是在举办激光灯光秀。 在最新的一场表演中，奶牛们弄到了一台强力的大型激光器——大到它们几乎无法把它从送达的位置移动走。它们希望能设法将激光器发出的光送到 FJ 农场另一侧的谷仓。激光器和谷仓都可以看作是位于二维平面上的点。奶牛们计划将激光器对准，使其发出的光束要么水平、要么垂直（即与 x 轴或 y 轴对齐）。随后，它们会让光束在若干面镜子上反射，从而将其引导至谷仓。 农场上有 $N$ 个栅栏立柱（$1 \leq N \leq 100,000$），位于互不相同的二维点上（且这些点也与激光器和谷仓的位置不同），奶牛可以在这些立柱上安装镜子。奶牛也可以选择不在某个立柱上安装镜子，此时激光会直接从立柱上方穿过而不改变方向。如果奶牛在某个立柱上安装镜子，它们会将镜子沿对角线方向摆放成 / 或 \ 的样子，使得水平光束会被改为垂直方向，或垂直光束会被改为水平方向。 请计算为了将激光引导到谷仓，奶牛最少需要使用多少面镜子。

输入格式

第一行包含 5 个用空格分隔的整数： $N, x_L, y_L, x_B, y_B$，其中 $(x_L, y_L)$ 是激光器的位置，$(x_B, y_B)$ 是谷仓的位置。所有坐标都在 $0$ 到 $1,000,000,000$ 之间。 接下来 $N$ 行每行包含一个栅栏立柱的 $x$ 和 $y$ 坐标，均为整数，范围为 $0 \ldots 1,000,000,000$。

输出格式

请输出将激光引导到谷仓所需的最少镜子数量；如果无法做到，则输出 -1。

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

1

提示

题目致谢：Brian Dean

标签: USACO|2016|Gold

来源

USACO|2016|Gold