#P18108. Minecraft Spiderweb
Minecraft Spiderweb
Minecraft Spiderweb
平面上有一个宽为 、高为 的矩形,四个顶点是 、、、。矩形边界上有 个互不相同的标记点。
你可以画任意多条水平或竖直线段。这些线段可以相交,也可以沿着矩形边界。要求所有标记点属于线段组成的同一个连通分量,也就是任意两个标记点之间都可以沿画出的线段到达。
求所需线段总长度的最小值。交叉点和其他连接点不必是给定的标记点。
输入格式
第一行包含测试用例数 ,。
每组测试用例第一行包含三个整数 ,其中
接下来 行,每行给出一个标记点的整数坐标 ,满足
保证所有点互不相同且位于矩形边界。点按沿矩形边界逆时针行走时的顺序给出,排序起点为左下角 :先经过下边、右边、上边,最后经过左边。不保证左下角本身是标记点。
所有测试用例的 之和不超过 。
输出格式
每组测试用例输出一个整数,表示最小总长度。
样例
3
1 2 1
1 0
2 1 2
0 0
1 2
3 2 2
1 0
2 1
0 1
0
3
3
一个标记点不需要画线。第二组两点的曼哈顿距离为3;第三组可以利用矩形内部的连接点达到总长度3。