向量匹配（Vector Matching）

题目背景

一组平面上的点可以两两配对，并为每一对点选择一个方向，从而得到若干向量。

不同的配对方式和方向选择，会让这些向量的合向量产生很大差异。现在，希望通过合理地配对所有点，使最终合向量的长度尽可能小。

题目描述

给定平面上的一个点集 $P$。点的数量 $n$ 为偶数，且所有点互不相同。

点集 $P$ 的一个向量匹配 $V$，是由 $\frac n2$ 个有向向量组成的集合，满足：

• 每个向量的起点和终点都是 $P$ 中的两个不同点；
• $P$ 中的每个点恰好出现一次：它要么是某个向量的起点，要么是某个向量的终点。

换言之，你需要把所有点两两配对，并为每一对点选择一个方向。

若一个向量从点 $(x_1,y_1)$ 指向点 $(x_2,y_2)$，则该向量为：

$$(x_2-x_1,\ y_2-y_1).$$

设向量匹配中的向量依次为：

$$(a_1,b_1),(a_2,b_2),\ldots,(a_{n/2},b_{n/2}),$$

则这些向量的和为：

$$\left( \sum_{i=1}^{n/2}a_i,\ \sum_{i=1}^{n/2}b_i \right).$$

其长度为：

$$\sqrt{ \left(\sum_{i=1}^{n/2}a_i\right)^2+ \left(\sum_{i=1}^{n/2}b_i\right)^2 }.$$

请在所有可能的向量匹配中，求出合向量长度的最小值。

输入格式

第一行包含一个偶数 $n$，表示点的数量。

接下来 $n$ 行，每行包含两个整数 $x_i,y_i$，表示第 $i$ 个点的坐标。

输出格式

输出一个实数，表示所有向量匹配中，合向量长度的最小值。

若你的答案与标准答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。

数据范围

对于所有测试数据：

• $2\le n\le 20$；
• $n$ 为偶数；
• $-100000\le x_i,y_i\le 100000$；
• 所有点两两不同。

样例 1

输入

4
-5 -5
-5 5
5 5
5 -5

输出

0.0

解释

一种最优匹配为：

• 从 $(-5,-5)$ 指向 $(-5,5)$，得到向量 $(0,10)$；
• 从 $(5,5)$ 指向 $(5,-5)$，得到向量 $(0,-10)$。

两个向量互为相反向量，因此它们的和为零向量，答案为 $0$。

样例 2

输入

2
-100000 -100000
100000 100000

输出

282842.71247461904

解释

只有两个点，因此只能由这两个点构成一个向量。无论选择哪个方向，向量长度均为：

$$\sqrt{200000^2+200000^2}.$$

样例 3

输入

10
26 -76
65 -83
78 38
92 22
-60 -42
-27 85
42 46
-86 98
92 -47
-41 38

输出

13.341664064126334

样例 4

输入

20
92383 -18240
42478 -56841
26103 57506
-51063 -22762
72172 -65260
-17487 -42804
22179 -34950
80130 27245
38797 -41611
-38546 -69322
24521 38655
-47024 -26671
-71456 54570
-20740 12287
63751 31971
-96441 15145
71347 4057
34233 70458
49104 56643
58014 -24482

输出

473.68871635283864