#1419. 分数规划

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Rhodoks

题目描述

czq有2n2n个正整数aia_i,他希望你用这2n2n个整数组成nn个分数,使得分数的和最小化。

每个分数的分母和分子各为一个czq的正整数且每个正整数用且仅使用一次。

输入格式

输入数据第一行仅一个整数nn,含义如题所述。

输入数据第二行包含2n2n个正整数,由空格隔开。

输出格式

输出一个浮点数,为答案。

你的答案被认为正确,当且仅当你的输出与标准答案的相对误差或者绝对误差不超过 10610^{−6}

形式化来说,假定你的输出答案是 xx,标准答案是 yy。你的输出被认为正确当且仅当 xymax(1,y)106\frac{|x−y|}{max(1,|y|)} \leq 10^{−6}

请注意精度问题,可以使用printf("%.10lf", x)来输出10位小数。

样例

样例输入

3
1 1 4 5 1 4

样例输出

0.7000000000

样例解释

一种可行的答案是14+15+14=0.7\frac{1}{4} + \frac{1}{5} + \frac{1}{4} = 0.7

数据范围与提示

1n1051 \leq n \leq 10^5

1ai1091 \leq a_i \leq 10^9