描述
经过了一整天的忙碌了后,Farmer John完全忘记了他把拖拉机留在了田地的中央了。他的奶牛们总是不怀好意,决定捉弄一下John:它们在田地里的不同位置放置了 $N$ 捆干草($1 ≤ N ≤ 50,000$),这样一来,John如果不先搬走一些干草,就无法轻易地把拖拉机开出来。
拖拉机的位置,以及 $N$ 捆干草的位置,都是二维平面上的点,坐标均为 1 到 1000 范围内的整数。拖拉机初始位置处没有干草。约翰驾驶拖拉机时,只能沿着平行于坐标轴的方向移动(北、南、东、西),并且每次移动的距离必须是整数。例如,他可以向北移动 2 个单位,再向东移动 3 个单位。拖拉机不能驶入有干草占据的点。
请帮助John计算出,他最少需要搬走多少捆干草,才能成功将拖拉机开出田地(即,使他能够将拖拉机开到二维平面的原点$(0,0)$)。
输入
输入的第一行是三个用空格隔开的整数,依次代表干草的堆数 $n$ 和拖拉机的起始坐标 $(x_0, y_0)$。
第 $2$ 行到第 $(n+1)$ 行,每行有两个用空格隔开的整数,第 $(i + 1)$ 行的整数 $x_i, y_i$ 代表第 $i$ 堆干草的坐标为 $(x_i, y_i)$。
输出
一行一个整数,表示最少要移动多少堆干草 John 才能将拖拉机开回坐标原点。
样例
- 复制
- 复制
提示
对于 $100\%$ 的数据,保证 $1 \leq n \leq 5 \times 10^4$,$1 \leq x_0, y_0, x_i, y_i \leq 10^3$。

关注我们