九条可怜最近接触到了攀岩这项运动。作为一名运动量接近为零的家里蹲，相比于动手攀岩，可怜显然更加享受攀岩运动中动脑的部分，即对攀岩路线的规划。
为了只动脑，可怜设计了一个简易的攀岩机器人来帮她动手。这个机器人由一个核心（大小可以忽略不计）和三个长度至多为 r 的可伸缩机械臂组成，如下图所示：

一面攀岩墙可以看成一个二维的无穷平面，上面有 n 个不同位置的岩点 p1​,…,pn​。在攀岩开始时，机器人的两个机械臂需要分别抓住岩点 p1​ 和 p2​，而其核心和第三个机械臂可以在任意位置。攀岩的目标是让机器人有两支机械臂同时抓握住岩点 pn​。
在攀岩过程中，机器人需要保证每时每刻都有两支机械臂抓握住两个不同的岩点。在满足这点的情况下，机器人可以在机械臂长度允许的情况下进行如下移动：

1. 连续地将核心的位置从当前位置移动到任意位置。
2. 用第三条机械臂抓握住一个岩点（可以与某条其他机械臂抓住相同的岩点）。
3. 让一条机械臂松开其抓握的岩点。注意，只有当另外两条机械臂已经抓握住不同岩点时，才能进行这项操作。

注：我们假设岩点的大小是无穷小，不会影响机器人的移动，比如机械臂、核心轨迹都可以经过岩点。
下面是一个攀岩过程的例子，假设平面上有四个岩点，坐标分别是 (0,0),(1,0),(0,1),(1,2)，则下面展示了一个 r=2​ 时，即机械臂长度至多为 2​ 时的攀岩方案。

1. 初始时，可怜将机器人的核心放在 (0.5,0) 处，第三根手臂随意地放在 (1,1) 处。
2. 机器人的第三机械臂抓握住岩点 p3​。
3. 机器人的第二机械臂松开，并移动到 (1,0.5) 处。
4. 机器人的核心移动至 (1,1)，此时第一机械臂的长度到达极限 2​。
5. 机器人的第二机械臂抓握住岩点 p4​。
6. 机器人的第一机械臂松开，并抓握住岩点 p4​，完成攀岩目标。

显然，机器人的机械臂长度越短，对可怜的路径规划能力要求越高。但是这个机械臂的长度也不能太短，不然机器人可能无论如何都无法完成攀岩任务。比如在上述任务中，如果机械臂长度小于 0.5，那么机器人将无法同时抓握 p1​ 和 p2​，这意味着它连开始攀岩都无法做到，更别说完成攀岩任务了。
因此，为了在合理范围内尽可能地挑战自己的大脑，可怜希望你对于攀岩馆中的每一项攀岩任务，都帮她计算（在可能完成攀岩任务的前提下）机械臂的最短长度是多少。

输入格式:

第一行输入一个整数 t (t≤100)，表示攀岩馆内攀岩任务的数量。
每个任务的第一行都是一个整数 n (3≤n≤1500)，表示攀岩任务涉及的岩点数量。
接下来 n 行，每行两个整数 (xi​,yi​)，表示第 i 个岩点的坐标。输入保证 0≤xi​,yi​≤106 且同一个攀岩任务中的岩点坐标两两不同。
输入保证满足 n>100 的数据不超过 3 组。

输出格式:

对于每个攀岩任务输出一行一个浮点数，表示最短可能的机械臂长度。你的答案在绝对误差或者相对误差不超过 10−6 的情况下都会被视为正确。

输入样例:

4
4
0 0
1 0
0 1
1 2
4
0 0
2 0
0 3
2 2
7
0 0
1 0
2 0
2 1
2 2
1 2
0 2
15
13 2
13 3
12 44
6 17
4 71
14 58
4 49
2 51
8 37
1 18
5 43
5 35
1 84
10 23
13 69

输出样例:

0.99999999498
1.41421355524
1.00000000498
10.13227667717

样例解释

第一组数据和题面中的攀岩任务一致，其最小机械臂长度为 1，而样例输出的答案在 10−6 的误差范围内，故会被视为正确。
下面给出了一个机械臂长度为 1 时的攀岩方案。攀岩开始时，机器人的核心与岩点 p1​ 重叠，第三机械臂在长度为 0 的情况下抓住了这个岩点，且第一机械臂额外抓住了岩点 p3​。接着，第三机械臂松开岩点 p1​，并随着核心移动至点 (1,1)。然后，第三机械臂伸出并抓握住岩点 p4​。最后，第二机械臂松开岩点 p2​ 并同样抓握住岩点 p4​，完成攀岩任务。

第二组数据中，最小机械臂长度为 2​，下图展示了一个对应的攀岩方案。攀岩开始时，机器人的核心位于 (1,1) 且三个机械臂分别抓握住岩点 p1​,p2​ 和 p4​。随后，第二机械臂松开点 p2​ 并抓握住岩点 p4​，完成攀岩任务。注意到此攀岩方案全程没有使用岩点 p3​，这也是被允许的：攀岩任务中不要求使用所有的岩点。

代码长度限制

16 KB

时间限制

4000 ms

内存限制

512 MB

栈限制

8192 KB

import java.util.*;
import java.io.*;

public class Main {
    // 快速输入类
    static class FastReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public FastReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreElements()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    return null;
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }

    static class Point {
        long x, y;
        Point(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }

    static class State implements Comparable<State> {
        int u, v;
        double r2;

        State(int u, int v, double r2) {
            this.u = u;
            this.v = v;
            this.r2 = r2;
        }

        @Override
        public int compareTo(State other) {
            return Double.compare(this.r2, other.r2);
        }
    }

    static long distSq(Point a, Point b) {
        return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
    }

    // 计算三角形最小覆盖圆半径平方
    
    static double getMinRadiusSq(int i, int j, int k, Point[] pts) {
        long a2 = distSq(pts[j], pts[k]);
        long b2 = distSq(pts[i], pts[k]);
        long c2 = distSq(pts[i], pts[j]);

        // 排序，使 a2 为最长边
        if (a2 < b2) { long tmp = a2; a2 = b2; b2 = tmp; }
        if (a2 < c2) { long tmp = a2; a2 = c2; c2 = tmp; }

        // 1. 钝角或直角三角形
        if (b2 + c2 <= a2) {
            return a2 / 4.0;
        }

        // 2. 锐角三角形 (外接圆公式)
        double da2 = (double) a2;
        double db2 = (double) b2;
        double dc2 = (double) c2;
        double den = 4.0 * db2 * dc2 - Math.pow(db2 + dc2 - da2, 2);
        return (da2 * db2 * dc2) / den;
    }

    static int getIdx(int u, int v, int n) {
        return (u < v) ? (u * n + v) : (v * n + u);
    }

    static void solve(FastReader sc, PrintWriter out) {
        String ns = sc.next();
        if (ns == null) return;
        int n = Integer.parseInt(ns);
        Point[] pts = new Point[n];
        for (int i = 0; i < n; i++) {
            pts[i] = new Point(sc.nextLong(), sc.nextLong());
        }

        if (n < 2) {
            out.printf("%.10f\n", 0.0);
            return;
        }

        // 状态数组，存储最小半径平方
        double[] d = new double[n * n];
        Arrays.fill(d, Double.MAX_VALUE);

        PriorityQueue<State> pq = new PriorityQueue<>();

        // 初始状态 (0, 1)
        int startId = getIdx(0, 1, n);
        d[startId] = distSq(pts[0], pts[1]) / 4.0;
        pq.add(new State(0, 1, d[startId]));

        double ans = Double.MAX_VALUE;

        while (!pq.isEmpty()) {
            State cur = pq.poll();
            int u = cur.u;
            int v = cur.v;
            double r2 = cur.r2;

            if (r2 > d[getIdx(u, v, n)]) continue;

            // 目标达成：任意一只手到达 n-1
            if (u == n - 1 || v == n - 1) {
                ans = r2;
                break;
            }

            for (int k = 0; k < n; k++) {
                if (k == u || k == v) continue;

                double neededR2 = getMinRadiusSq(u, v, k, pts);
                double nextR2 = Math.max(r2, neededR2);

                // 尝试移动 v 变为 k
                int idUK = getIdx(u, k, n);
                if (nextR2 < d[idUK]) {
                    d[idUK] = nextR2;
                    pq.add(new State(u, k, nextR2));
                }

                // 尝试移动 u 变为 k
                int idVK = getIdx(v, k, n);
                if (nextR2 < d[idVK]) {
                    d[idVK] = nextR2;
                    pq.add(new State(v, k, nextR2));
                }
            }
        }
        out.printf("%.10f\n", Math.sqrt(ans));
    }

    public static void main(String[] args) {
        FastReader sc = new FastReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        String ts = sc.next();
        if (ts != null) {
            int t = Integer.parseInt(ts);
            while (t-- > 0) {
                solve(sc, out);
            }
        }
        out.flush();
    }
}