钻石矿工是一款与黄金矿工类似的游戏,但这款游戏中有 $$$n$$$ 矿工,而不是 $$$1$$$。
矿区可以用平面来形容。 $$$n$$$ 矿工可以被视为 y 轴上的 $$$n$$$ 点。矿区内有$$$n$$$钻石矿。我们可以将它们视为 x 轴上的 $$$n$$$ 点。由于某种原因,没有矿工或钻石矿位于原点(点 $$$(0, 0)$$$)。
每个矿工都应该开采一个钻石矿。每个矿工都有一个钩子,可以用来开采钻石矿。如果 $$$(a,b)$$$ 点的矿工使用他的钩子在 $$$(c,d)$$$ 点开采钻石矿,他将花费 $$$\sqrt{(a-c)^2+(b-d)^2}$$$ 能量来开采它(这些点之间的距离)。矿工们不能移动或互相帮助。
这个游戏的目标是最小化矿工花费的能量总和。你能找到这个最小值吗?
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 矿工和矿场的数量。
接下来的 $$$2n$$$ 行包含两个空格分隔的整数 $$$x$$$ ($$$-10^8 \le x \le 10^8$$$) 和 $$$y$$$ ($$$-10^8 \le y \le 10^8$$$),它们代表点 $$$(x,y)$$$ 来描述矿工或钻石矿的位置。要么 $$$x = 0$$$,表示在 $$$(0, y)$$$ 点有一个矿工,要么 $$$y = 0$$$,表示在 $$$(x, 0)$$$ 点有一个钻石矿。同一点可以有多个矿工或钻石矿。
保证没有点位于原点。保证 x 轴上的点数等于 $$$n$$$,y 轴上的点数等于 $$$n$$$。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,打印一个实数——应该消耗的最小能量总和。
如果您的答案的绝对或相对误差不超过 $$$10^{-9}$$$,则视为正确。
正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-9}$$$ 时,您的答案才会被接受。
示例
输入 #1
3 2 0 1 1 0 0 -1 -2 0 4 1 0 3 0 -5 0 6 0 0 3 0 1 0 2 0 4 5 3 0 0 4 0 -3 4 0 2 0 1 0 -3 0 0 -10 0 -2 0 -10
输出 #1
3.650281539872885 18.061819283610362 32.052255376143336
注意
在第一个测试用例中,矿工位于 $$$(0,1)$$$ 和 $$$(0,-1)$$$,而钻石矿位于 $$$(1,0)$$$ 和 $$$(-2,0)$$$。如果按照如图所示的方式安排矿工获取钻石矿,则可以获得能量$$$\sqrt2 + \sqrt5$$$ 的总和。