P3036 [USACO16DEC] Lasers and Mirrors G
题目描述
出于某种原因,Farmer John 的奶牛似乎总是在举办激光表演。
在它们的最新表演中,奶牛们获得了一台大型强力激光器——事实上,这台激光器太大,以至于它们无法轻易从交付地点移动它。它们希望以某种方式将激光器的光束发送到 Farmer John 的农场另一边的谷仓。激光器和谷仓都可以被视为位于 Farmer John 农场地图的二维平面中的点。奶牛们计划将激光器指向水平或垂直方向(即与 $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。