该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P2873 [USACO07DEC] Mud Puddles S

题目描述

农夫约翰在早上 $6$ 点准时离开家去挤奶贝茜。然而，前一天晚上下了大雨，田地里非常泥泞。约翰从坐标平面上的点 $(0,0)$ 出发，前往位于 $(X,Y)$ 的贝茜（$-500\le X\le 500$；$-500\le Y\le 500$）。他可以看到田地上所有 $N(1\le N\le 10,000)$ 个泥坑，位于点 $(A_i,B_i)$（$-500\le A_i\le 500$；$-500\le B_i\le 500$）。每个泥坑只占据它所在的点。

刚买了新靴子的农夫约翰绝对不想弄脏他的靴子，但他也想尽快到达贝茜。他已经迟到了，因为他不得不数清所有的泥坑。如果农夫约翰只能平行于坐标轴行走，并且只能在整数坐标点处转弯，那么他到达贝茜并保持靴子干净的最短距离是多少？总会有一条没有泥的路径可以让农夫约翰到达贝茜。

输入格式

• 第 $1$ 行：三个用空格分隔的整数：$X,Y,N$。
• 第 $2$ 行到第 $N+1$ 行：第 $i+1$ 行包含两个用空格分隔的整数：$A_i$ 和 $B_i$。

输出格式

• 第 $1$ 行：农夫约翰到达贝茜而不踩到泥的最短距离。

输入输出样例 #1

输入 #1

1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2

输出 #1

11

说明/提示

题面翻译由 ChatGPT-4o 提供。