← 返回题目列表

Codeforces · 1495/A

A. 钻石矿工

中文机器翻译题面 查看原题

钻石矿工是一款与黄金矿工类似的游戏,但这款游戏中有 $$$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$$$ 的总和。