激光表演
时间限制: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