/ Vijos / 题库 /

激光表演

激光表演

时间限制:1秒  内存限制:256M


【题目描述】

  出于某种原因,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。

【输入输出样例】

 Input

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

 Output

1

【数据限制】

【来源】

  Mr.he

信息

ID
3133
难度
(无)
分类
图结构 | 最短路 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者