{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e最近点对问题是计算几何中一个众所周知的问题。在这个问题中,给定了欧几里德平面上的$n$个点,你需要找到一对距离最近的点。\u003cbr\u003e\u003cbr\u003e现在,多年参加编程比赛的聪明的 Clairs 正在尝试解决一个更难的问题,名为最近线段对问题,其描述与上述问题类似。\u003cbr\u003e\u003cbr\u003e然而,这个问题对于 Clairs 来说似乎太难了,她请求你的帮助。\u003cbr\u003e\u003cbr\u003e现在欧几里德平面上有$n$条线段,你需要选择两条不同的线段,然后在这两条线段上分别选择一个点,使得这两个点之间的距离最小。\u003cbr\u003e\u003cbr\u003e为简单起见,任意给定的两条线段没有公共点,你不需要展示选定的两个点,而只需展示它们之间的距离。\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入包含多个测试用例,第一行包含一个整数$T~(1 \\le T \\le 200)$,表示测试用例的数量。\u003cbr\u003e\u003cbr\u003e对于每个测试用例,第一行包含一个整数$n~(2 \\le n \\le 10\\,000)$,表示欧几里德平面上线段的数量。\u003cbr\u003e\u003cbr\u003e接下来的$n$行描述了欧几里德平面上的所有线段,其中第$i$行包含四个整数$x_1, y_1, x_2$和$y_2$,描述连接$(x_1,y_1)$和$(x_2,y_2)$的线段,其中$-10^9 \\le x_1, y_1, x_2, y_2 \\le 10^9$。\u003cbr\u003e\u003cbr\u003e保证每个线段的两个端点不重合,在每个测试用例中任意给定的两条线段不相交,并且不会有超过$20$个测试用例满足$n\u0026gt;1\\,000$。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出一行包含一个实数,表示最近线段对问题的答案,绝对或相对误差不超过$10^{-6}$。\u003cbr\u003e\u003cbr\u003e具体来说,假设你的答案是$a$,评委的答案是$b$,只有当$\\frac{|a - b|}{\\max\\{1, |b|\\}} \\le 10^{-6}$时你的答案才被认为是正确的。\u003cbr\u003e"}},{"title":"样例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n2\r\n0 1 1 2\r\n1 1 2 0\r\n2\r\n0 1 1 2\r\n2 2 3 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.707106781187\r\n1.000000000000\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}