#P18108. Minecraft Spiderweb

Minecraft Spiderweb

Minecraft Spiderweb

平面上有一个宽为 WW、高为 HH 的矩形,四个顶点是 (0,0)(0,0)、(W,0)(W,0)、(W,H)(W,H)、(0,H)(0,H)。矩形边界上有 nn 个互不相同的标记点。

你可以画任意多条水平或竖直线段。这些线段可以相交,也可以沿着矩形边界。要求所有标记点属于线段组成的同一个连通分量,也就是任意两个标记点之间都可以沿画出的线段到达。

求所需线段总长度的最小值。交叉点和其他连接点不必是给定的标记点。

输入格式

第一行包含测试用例数 tt,1≤t≤2⋅1051\le t\le2\cdot10^5。

每组测试用例第一行包含三个整数 n,W,Hn,W,H,其中

1≤n≤106,1≤W,H≤109.1\le n\le10^6,\qquad1\le W,H\le10^9.

接下来 nn 行,每行给出一个标记点的整数坐标 xi,yix_i,y_i,满足

0≤xi≤W,0≤yi≤H.0\le x_i\le W,\qquad0\le y_i\le H.

保证所有点互不相同且位于矩形边界。点按沿矩形边界逆时针行走时的顺序给出,排序起点为左下角 (0,0)(0,0):先经过下边、右边、上边,最后经过左边。不保证左下角本身是标记点。

所有测试用例的 nn 之和不超过 10610^6。

输出格式

每组测试用例输出一个整数,表示最小总长度。

样例

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。