luogu#P1849. [USACO12MAR] Tractor S

    ID: 5904 远端评测题 2000ms 128MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>字符串图论贪心2012USACO枚举暴力

[USACO12MAR] Tractor S

题目描述

经过一天漫长的工作,农场主 John 完全忘记了他的拖拉机还在场地中央。他的奶牛们总喜欢和他搞些恶作剧,它们在场地的不同位置丢下 nn 堆干草。这样 John 就必须先移走一些干草堆才能将拖拉机开走。

拖拉机和干草堆都可以看作是二维平面上的点,它们的坐标都是整数,没有哪堆干草的坐标和拖拉机的初始坐标一致。John 驾驶拖拉机只能沿着坐标轴的方向移动若干单位长度,比如说,他可以先朝北移动 22 个单位长度,再向东移动 33 个单位长度等等。拖拉机不能移动到干草堆所占据的点。

请你帮助 John 计算一下,最少要移动多少堆干草才能将拖拉机开回坐标原点。

输入格式

输入的第一行是三个用空格隔开的整数,依次代表干草的堆数 nn 和拖拉机的起始坐标 (x0,y0)(x_0, y_0)

22 行到第 (n+1)(n+1) 行,每行有两个用空格隔开的整数,第 (i+1)(i + 1) 行的整数 xi,yix_i, y_i 代表第 ii 堆干草的坐标为 (xi,yi)(x_i, y_i)

输出格式

一行一个整数,表示最少要移动多少堆干草 John 才能将拖拉机开回坐标原点。

7 6 3 
6 2 
5 2 
4 3 
2 1 
7 3 
5 4 
6 4 
1 

提示

对于 100%100\% 的数据,保证 1n5×1041 \leq n \leq 5 \times 10^41xi,yi1031 \leq x_i, y_i \leq 10^3