题目描述

在与联盟的战斗中屡战屡败后，帝国撤退到了最后一个据点。

依靠其强大的防御系统，帝国击退了联盟的六波猛烈进攻。

经过几天的苦思冥想，联盟将军亚瑟终于注意到帝国防御系统唯一的弱点就是能源供应。

该系统由 N 个核电站供应能源，其中任何一个被摧毁都会使防御系统失效。

将军派出了 N 个特工进入据点之中，打算对能源站展开一次突袭。

不幸的是，由于受到了帝国空军的袭击，他们未能降落在预期位置。

作为一名经验丰富的将军，亚瑟很快意识到他需要重新安排突袭计划。

他现在最想知道的事情就是哪个特工距离其中任意一个发电站的距离最短。

你能帮他算出来这最短的距离是多少吗？

输入格式

输入中包含多组测试用例。

第一行输入整数 T，代表测试用例的数量。

对于每个测试用例，第一行输入整数 N。

接下来 N 行，每行输入两个整数 X 和 Y，代表每个核电站的位置的 X，Y 坐标。

在接下来 N 行，每行输入两个整数 X 和 Y，代表每名特工的位置的 X，Y 坐标。

输出格式

每个测试用例，输出一个最短距离值，结果保留三位小数。

每个输出结果占一行。

样例

2
4
0 0
0 1
1 0
1 1
2 2
2 3
3 2
3 3
4
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

1.414
0.000

数据范围

• $1≤N≤100000$
• $0≤X,Y≤1000000000$

来源

• poj3714
• 算法竞赛进阶指南