题目名称 692. [USACO Mar12] 拖拉机
输入输出 tractor.in/out
难度等级
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 GravatarMakazeu 于2012-03-31加入
开放分组 全部用户
提交状态
分类标签
USACO 双端队列 最短路 搜索法 01BFS
分享题解
通过:35, 提交:74, 通过率:47.3%
Gravatarlihaoze 100 0.082 s 6.60 MiB C++
Gravatarkaaala 100 0.101 s 2.26 MiB C++
GravatarLethur 100 0.101 s 2.26 MiB C++
Gravatarムラサメ 100 0.120 s 14.14 MiB C++
Gravatarforever 100 0.160 s 2.03 MiB C++
Gravatarkaaala 100 0.198 s 2.21 MiB C++
Gravatarkaaala 100 0.198 s 2.21 MiB C++
Gravatarlavey 100 0.219 s 29.00 MiB C++
Gravatar00000 100 0.222 s 29.00 MiB C++
GravatarWHZ0325 100 0.244 s 8.01 MiB C++
本题关联比赛
EYOI与SBOI开学欢乐赛1st
关于 拖拉机 的近10条评论(全部评论)
为什么vis数组赋值位置不同就会E呢??
Gravatarforever
2015-10-29 21:07 4楼
我翻譯的試題竟然還有人看懂。。。
GravatarMakazeu
2012-10-22 15:02 3楼
ORZ帆儿。。
Gravatar苏轼
2012-10-22 11:30 2楼
数据弱爆了,渣渣题啊= =
Gravatarkaaala
2012-03-31 15:12 1楼

692. [USACO Mar12] 拖拉机

★   输入文件:tractor.in   输出文件:tractor.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目描述】

$Translated$ $by$ $Makazeu$

在一天的工作结束之后,农夫$John$完全忘记了他的拖拉机——他把他的拖拉机落在了田野的中央。

他的奶牛永远都不怀好意($up$ $to$ $no$ $good$),决定跟$FJ$玩个恶作剧:

他们在田地里的很多地方堆积了一共$N$捆干草,所以$FJ$在不先移除($remove$)这些干草堆的情况下无法很容易的移走($remove$)他的拖拉机。

这个拖拉机的位置,和这$N(1<=N<=50000)$个干草堆的位置都在一个二维平面内,用$1~1000$的整数坐标来描述。

没有一个干草的位置在拖拉机的初始位置($initial$ $position$)。

当$FJ$驾驶着他的拖拉机时,他仅能平行于坐标轴$(parallel$ $to$ $the$ $coordinate$ $axes$,东、西、南、北)移动,

而且他必须按照整数序列移动$(move$ $in$ $a$ $sequence$ $of$ $integer$ $amounts)$。

例如,他可以向南移动$2$个单位,然后向东移动$3$个单位。拖拉机不能移动到有干草堆的位置。

请帮助$FJ$决定一下他最少需要移走多少干草堆才能使他自由的移走他的拖拉机(也就是说,他能把他的拖拉机移动到平面坐标系的原点。译者补充:可以先移动到边界以外,然后绕到原点)


【输入格式】

*第$1$行:三个用空格分隔开的整数$N$和拖拉机的起始位置$x,y$。

*第$2~1+N$行:每行包括两个整数$(x,y)$表示每个干草堆的位置。

【输出格式】

*第一行:最小移走干草堆的数。

【样例输入】

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

【样例输出】

1

【样例说明】

输入解释:

拖拉机开始在$(6,3)$。一共有$7$堆干草,分别位于$(6,2),(5,2),(4,3),(2,1),(7,3),(5,4)和(6,4)$。

输出解释:

$FJ$只需要移走一堆干草即可移走他的拖拉机。

【来源】

USACO 2012 March Contest Silver Divison

Problem 1