当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器：

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6385：rect

题目描述
度度熊有一个大小为 $MX \times MY$ 的矩形，左下角坐标为 $(0, 0)$，右上角坐标为 $(MX, MY)$。此矩形内有 $N$ 个整数坐标的点 $(x_i, y_i)$，$x_i$ 彼此不重复，$y_i$ 彼此也不重复。

现在要从每一个点画出一条线段，满足下列条件：

* 线段起点为坐标点，终点在矩形范围的四个边界之一上。
* 线段彼此不能交叉。

现在要让画出的线段的长度总和最小，请输出这个最小的长度总和值。
输入解释
输入的第一行有一个正整数 $T$，代表接下来有几笔测试资料。

对于每笔测试资料：
第一行有三个整数 $MX$, $MY$ 以及 $N$。
接下来的 $N$ 行每行有两个正整数 $x_i$ 及 $y_i$。

* $2 \le MX, MY \le 10^6$
* $0 \le N \le 10^5$
* 如果 $i \ne j$，则保证 $x_i \ne x_j$ 及 $y_i \ne y_j$
* $0 < x_i < MX$
* $0 < y_i < MY$
* $1 \le T \le 20$
* 至多 $2$ 笔测试资料中的 $N > 1000$
输出解释
对于每一笔测试资料，请依序各自在一行内输出一个整数，代表可能的最小长度和。
输入样例 
2
4 4 1
2 2
10 7 3
6 3
2 6
9 5
输出样例 
2
5
来自杭电HDUOJ的附加信息
Recommend chendu
该题目是Virtual Judge题目，来自 杭电HDUOJ
题目来源 2018 “百度之星”程序设计大赛 - 初赛（B）
源链接： HDU-6385
最后修改于 2020-10-25T23:30:53+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
时间上限 内存上限
2000/1000MS(Java/Others) 131072/131072K(Java/Others)