Problem 3068 --Closest Pair of Segments

3068: Closest Pair of Segments

上一题 正确率: $0.00\%$ 下一题
"
Time Limit $20$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $1$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

The closest pair of points problem is a well-known problem of computational geometry. In this problem, you are given n points in the Euclidean plane and you need to find a pair of points with the smallest distance between them.

Now, Claris, the brilliant one who has participated in programming contests for several years, is trying to solve a harder problem named the closest pair of segments problem, which also has a quite simple description as above.

However, the problem seems even too hard for Claris and she is asking you for help.

Now n segments are lying on the Euclidean plane, you are asked to pick two different segments and then pick a point on the two segments respectively to minimize the distance between these two points.

For simplicity, any two given segments share no common point, and you don't need to show her the two chosen points, but the distance between them instead.

Input

The input contains several test cases, and the first line contains a single integer T (1≤T≤200), the number of test cases.
For each test case, the first line contains one integer n (2≤n≤10000), which is the number of segments on the Euclidean plane.
The following n lines describe all the segments lying on the Euclidean plane, the i-th of which contains for integers x1,y1,x2 and y2 describing a segment that connects (x1,y1) and (x2,y2), where −109≤x1,y1,x2,y2≤109.
It's guaranteed that the two endpoints of each segment do not coincide, any two given segments do not intersect with each other in each test case, and no more than 20test cases satisfy n>1000.

Output

For each test case, output a line containing a single real number for the answer to the closest pair of segments problem with an absolute or relative error of at most 10−6.

Precisely speaking, assume that your answer is a and and the jury's answer is b, your answer will be considered correct if and only if |a−b|max{1,|b|}≤10−6.

Sample Input复制

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

Sample Output复制

0.707106781187
1.000000000000

推荐代码 查看3068 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战 淡意的温柔 588051 2020-05-27 09:38:35

赛题来源/所属竞赛 2019 Multi-University Training Contest 10 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛