配点: 100 点
去年年底,圣诞老人忘记给JOI村的孩子们送圣诞礼物。所以,作为道歉,我决定给孩子们送巧克力蛋糕。明天交货期就快到了,是时候考虑一下旅行计划了。
JOI村南北笔直延伸。 W 一条真正的从东向西笔直延伸的道路。 H 道路被分成棋盘形状的部分。 W 在主要道路上,有 1,2,\ldots,W 并按东西方向编号。 H 这条路上,有 从西边编号为 1,2,\ldots,H 。 x 南北向南路 y 东西路交叉口 由 (x, y) 代表。 JOI村有 N 有一所房子 圣诞老人只能沿着道路移动。相邻交叉路口之间行驶所需的时间为 1 。
JOI村的每家每户都有一个孩子,所以圣诞老人会拜访JOI村的每家每户。 1 他们必须将巧克力蛋糕一件一件地交付。由于带着珍贵的巧克力蛋糕带着驯鹿飞来飞去有点危险,圣诞老人和驯鹿决定降落在JOI村的一个十字路口,圣诞老人将从那里步行并送出巧克力蛋糕。同时圣诞老人也会送来巧克力蛋糕。 我走路时不会携带超过 2 的巧克力蛋糕。换句话说,圣诞老人吃的是巧克力蛋糕。 1 每次送货到家,我都会回到下车的路口。
圣诞老人决定选择一个旅行计划,尽量减少从降落 JOI 村到将巧克力蛋糕送到每户人家所需的时间。注意,从把巧克力蛋糕送到最后一间房子到回到下车的路口所需的时间不包括在所需时间中。另外,除了旅行所需的时间之外,不要考虑任何其他事情。
課題
给定房屋位置信息,编写一个程序,求从降落在JOI村到将巧克力蛋糕送到所有房屋所需的最短时间,以及圣诞老人应该降落的路口位置,以最小化时间,假设圣诞老人下车的路口选择得很好。
制限
| 1\leqq W\leqq 1\,000\,000\,000\,(=10^9) | 南北方向延伸的道路数量 |
| 1\leqq H\leqq 1\,000\,000\,000\,(=10^9) | 东西方向延伸的道路数量 |
| 1 \leqq N \leqq 100\,000\, (=10^5) | 房屋数量 |
| 1 \leqq X_i \leqq W | i 第号房屋所在地南北方向延伸的道路编号 |
| 1 \leqq Y_i \leqq H | i 第号房屋所在地东西方向延伸的道路编号 |
入力
从标准输入读取以下输入。
- 1 第 1 行包含一个整数,表示每个方向的道路数量。 W, H 以空格作为分隔符。
- 2 第一行是一个整数,表示房屋数量。 写入 N 。
- 继续 N 行包含有关房屋位置的信息。i + 2 行目 (1 \leqq i \leqq N) 是一个整数 X_i,Y_i 以空格作为分隔符写入,i 第号房子是路口 表明它位于 (X_i, Y_i) 。这些 所有 N 交叉点都不同。
出力
将以下数据输出到标准输出。
- 1 线表示所需的最短时间。 1 必须写入整数。
- 2 行中显示了您应该下车以尽量减少行驶时间的交叉路口。 当 (x, y) 时,2 整数 x, y 必须按此顺序写入,并用空格分隔。如果有多个合适的交叉路口,则选择最西边的交叉路口(即 如果x 的值很小),交集仍然是 1 ,然后是其中最南端(即y 值较小)选择交点。
注意
在这个问题中,要处理的整数范围是 32 请注意,它可能不适合位。
採点基準
评分数据中,分配的分数 40 对于%,N \leqq 1\,000 成立。
评分数据中,分配的分数 10 对于%,W\leqq 50,H\leqq 50,N\leqq 1\,000 成立。
入力例 1
5 4 3 1 1 3 4 5 3
出力例 1
10 3 3
例如,以下旅行计划可以最大限度地减少所需时间。 在
- 交差点 (3, 3) 下车。 将巧克力蛋糕送到位于
- 交差点 (3, 4) 的房子。到目前为止经过的时间是 返回到 1 。
- 交差点 (3, 3) 。到目前为止经过的时间是 2 。
- 交差点 (5, 3) 的房子。到目前为止经过的时间是 返回到 4 。
- 交差点 (3, 3) 。到目前为止经过的时间是 6 。
- 交差点 (1, 1) 的房子。到目前为止经过的时间是 返回到 10 。
入力例 2
4 6 8 1 3 3 2 4 4 2 5 2 3 3 3 3 4 2 4
出力例 2
21 2 3
注意,你可以在房子所在的路口下车。