网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[USACO Dec07]泥潭
成绩 | 0 | 开启时间 | 2013年01月18日 星期五 09:40 |
折扣 | 0.8 | 折扣时间 | 2013年01月18日 星期五 09:40 |
允许迟交 | 是 | 关闭时间 | 2013年01月18日 星期五 09:40 |
输入文件 | mud.in | 输出文件 | mud.out |
译 by CmYkRgB123
描述
Farmer John在早晨6点准时去给贝茜挤奶,然而昨天晚上下了大雨,他的牧场变得泥泞不堪了。Farmer John的家在坐标平面的 (0,0) 处,贝茜在 (X, Y) (-500 ≤ X ≤ 500; -500 ≤ Y ≤ 500)。他看见了所有的 N (1 ≤ N ≤ 10,000) 个泥潭,分别在 (Ai, Bi) (-500 ≤ Ai ≤ 500; -500 ≤ Bi ≤ 500) 。每个泥潭只占一个点的位置。
Farmer John 刚刚买了新的靴子,他绝对不想把靴子踩进泥潭弄脏,而他又想尽快的找到贝茜。他已经快晚了,因为他花了大量的时间来找到所有的泥潭的位置。 Farmer John 只能平行于坐标轴移动,每次移动一个单位。请你帮助 Farmer John 找到一条路,使得 Farmer John 能够最快的找到贝茜,而且不会弄脏靴子。我们约定一定存在一条路使 Farmer John 找到贝茜。
输入
* 第 1 行: 三个整数 X, Y, N
* 第 2..N+1 行: 第 i+1 行 包含两个整数 Ai , Bi
输出
* 第 1 行: Farmer John 能够最快的找到贝茜,而且不会弄脏靴子,要走的最小的距离。
样例输入
1 2 7 0 2 -1 3 3 1 1 1 4 2 -1 1 2 2
样例输出
11