## 1) Abridged problem statement

- You are given `n` points (oases) in the plane, all distinct, and not all collinear.
- A caravan travels from oasis `s` to oasis `t` at constant speed along a polyline going through oases.
- Among all routes from `s` to `t`, the caravan chooses one that minimizes the **maximum length of any segment** of the route (equivalently, minimizes the maximum time spent outside oases).
- You are given `q` queries `(s_i, t_i)`.
  For each, output that minimal possible value of the longest segment on an optimal path from `s_i` to `t_i`, with absolute/relative error ≤ 1e-9.

---

## 2) Detailed editorial

### 2.1 Reformulation

- You have `n` points in the plane.
- You can move along straight segments connecting oases; you may choose any sequence of intermediate oases.
- For a path `s = v0, v1, ..., vk = t`, define its **bottleneck** as `max length(vi, v{i+1})`.
- Among all `s-t` paths, you want the minimum possible bottleneck. Call this value `ans(s, t)`.

If we define an undirected, complete graph on the oases with edge weights equal to Euclidean distances, the problem is:

> For each pair `(s, t)`, find the minimum possible maximum-edge-weight over all paths from `s` to `t` in this graph.

This is the classic **minimax path** or **minimum bottleneck path** problem.

### 2.2 MST minimax property

A key graph-theoretical fact:

> In a connected weighted undirected graph, for any two nodes `u, v`, if you take **any minimum spanning tree (MST)** of the graph, then the **unique path in the MST** from `u` to `v` has:
>
> - maximum edge weight equal to the minimum possible maximum edge weight over all `u-v` paths in the original graph.

So `ans(s, t)` = maximum edge on the unique `s-t` path in the Euclidean MST.

Thus we need:

1. The Euclidean MST on `n` points.
2. For each query `(s, t)`, the maximum edge on the `s-t` path in this MST.

However, the input size can be large and the graph is **complete** (`O(n^2)` edges), which is too big.

We need a way to:
- Avoid enumerating all `n^2` edges, but
- Still build the MST correctly.

### 2.3 Euclidean MST via Delaunay/Voronoi

For points in the plane, the Euclidean MST is a subgraph of the **Delaunay triangulation** of the points.

- Delaunay triangulation edges have the property that for each edge, there exists an empty circumcircle touching the two endpoints and containing no other point inside.
- The Euclidean MST uses only Delaunay edges. Thus if we compute all Delaunay edges, we can run Kruskal on only these edges instead of on all `n^2` pairs.

The dual of the Voronoi diagram is the Delaunay triangulation:

- Given a Voronoi diagram of the sites (oases), connect two sites whose Voronoi cells share an edge. Those edges form the Delaunay triangulation.

So the strategy:

1. Compute the Voronoi diagram (Fortune's sweep-line algorithm).
2. From it, obtain all Delaunay edges: every pair `(i, j)` of sites that are neighbors in the Voronoi diagram.
3. Run MST (Kruskal) using these edges.
4. Answer minimax path queries on the MST.

The provided solution implements step 1 via a custom `VoronoiDiagram` class using a sweep-line method; it returns all neighboring site pairs (`edges`).

### 2.4 Avoiding LCA / Heavy Preprocessing: Parallel Binary Search

We want, for each query `(s, t)`, the maximum edge weight on the path between them in the MST.

A natural approach is to build the MST, root it, and do LCA with binary lifting while maintaining maximum-edge-on-path. That would be `O((n + q) log n)` and works fine.

But the provided solution instead does:

- **Parallel binary search on the edge index during Kruskal-like DSU sweeps**.

Procedure:

1. Let `E` be the list of Delaunay edges between oases, sorted in nondecreasing order of squared Euclidean length.
2. Each query `i` will ultimately correspond to some index `pos_i` in this sorted `E` where `s_i` and `t_i` first become connected if we union edges from `0` upward.

Interpretation:

- If you process edges `E[0..k]`, DSU tells you which vertices are connected using edges of length ≤ `weight(E[k])`.
- For query `(s, t)`, if `s` and `t` are connected at step `k`, then `ans(s, t) ≤ length(E[k])`.
- The smallest `k` for which they are connected is exactly the maximum edge weight on their MST path, in terms of index.

So we want minimal `k` such that `s` and `t` are in the same DSU component when using edges `0..k`.

We can binary search this index for each query, but doing `q` independent binary searches `O(q log |E|)` and rebuild DSU each time (`O(|E|)` per binary search) would be too big: `O(q |E| log |E|)`.

Instead, we do **parallel binary search**:

- Maintain `low[i]` and `high[i]` (over edge indices) for each query `i`, the search range for the minimal connecting edge index.
- Repeatedly:
  - Build DSU from scratch, then scan edges `E[0..]` once.
  - For each edge index `e`, apply union; then process all queries whose current mid candidate equals `e`.
  - If, at index `e`, `s` and `t` are connected, we know the answer index is ≤ `e`, so `high[i] = e - 1`.
  - Otherwise `low[i] = e + 1`.
- Each iteration cuts the range roughly in half for each unresolved query.
- After `O(log |E|)` sweeps, all `low[i] > high[i]`, meaning we have determined the boundary index `pos_i = high[i] + 1`.

Total cost:

- About `O((|E| + q) log |E|)` DSU operations, which is feasible since `|E|` is linear in `n` for Delaunay triangulation.

Edge case: when `s_i == t_i`, answer is 0.0 regardless of the MST edges. The code handles this specially.

### 2.5 Geometry implementation details

The solution uses:

- `struct Point` with:
  - Coordinates `x, y` as `long double` (`coord_t`).
  - Basic vector operations, dot product `*`, cross product `^`, norm, rotate, etc.
  - Functions like `ccw`, `line_line_intersection`, `circumcenter`, etc.

`VoronoiDiagram`:

- Implements a beach-line based algorithm (Fortune's algorithm).
- Keeps a **beach line** as a `multiset<Arc>` ordered by the y-coordinate of the locus of each arc at the current sweep line `x`.
- Cloning the full correctness of Voronoi is complex, but the key:
  - It computes which sites are neighbors in the Voronoi diagram.
  - For each such neighbor pair `(i, j)`, it records an edge `(i, j)` in `edges`.

These edges are exactly the edges of the corresponding Delaunay triangulation up to some boundary issues, but good enough for MST.

Before computing the Voronoi diagram, the points are rotated by 1 radian about the origin to avoid degeneracies like aligned points leading to numeric instability.

After building the Voronoi diagram and extracted edges, the code:

1. Sorts `edges` by squared Euclidean distance.
2. Parallel-binary-searches over these sorted edges to answer queries.

Finally, to print answers:

- For each query `i`:
  - If `s == t`, print `0.0`.
  - Else, the smallest connecting index is `pos_i = high[i] + 1`.
  - Let that edge be `(u, v) = edges[pos_i]`.
  - Print Euclidean distance `|u - v|` with 10 decimal places.

Remember: Although we reason in terms of MST, the code *never explicitly builds the MST tree structure*; it only relies on the order of edges and connectivity in DSU to deduce the bottleneck edge needed for each pair.

---

## 3) C++ Solution

```cpp
#include <bits/stdc++.h>
// #include <coding_library/geometry/point.hpp>
// #include <coding_library/geometry/voronoi.hpp>
// #include <coding_library/graph/dsu.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

using coord_t = long double;

struct Point {
    static constexpr coord_t eps = 1e-12;

    coord_t x, y;
    Point(coord_t x = 0, coord_t y = 0) : x(x), y(y) {}

    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    Point operator*(coord_t c) const { return Point(x * c, y * c); }
    Point operator/(coord_t c) const { return Point(x / c, y / c); }

    coord_t operator*(const Point& p) const { return x * p.x + y * p.y; }
    coord_t operator^(const Point& p) const { return x * p.y - y * p.x; }

    bool operator==(const Point& p) const { return x == p.x && y == p.y; }
    bool operator!=(const Point& p) const { return x != p.x || y != p.y; }
    bool operator<(const Point& p) const {
        return x != p.x ? x < p.x : y < p.y;
    }
    bool operator>(const Point& p) const {
        return x != p.x ? x > p.x : y > p.y;
    }
    bool operator<=(const Point& p) const {
        return x != p.x ? x < p.x : y <= p.y;
    }
    bool operator>=(const Point& p) const {
        return x != p.x ? x > p.x : y >= p.y;
    }

    coord_t norm2() const { return x * x + y * y; }
    coord_t norm() const { return sqrt(norm2()); }
    coord_t angle() const { return atan2(y, x); }

    Point rotate(coord_t a) const {
        return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
    }

    Point perp() const { return Point(-y, x); }
    Point unit() const { return *this / norm(); }
    Point normal() const { return perp().unit(); }
    Point project(const Point& p) const {
        return *this * (*this * p) / norm2();
    }
    Point reflect(const Point& p) const {
        return *this * 2 * (*this * p) / norm2() - p;
    }

    friend ostream& operator<<(ostream& os, const Point& p) {
        return os << p.x << ' ' << p.y;
    }
    friend istream& operator>>(istream& is, Point& p) {
        return is >> p.x >> p.y;
    }

    friend int ccw(const Point& a, const Point& b, const Point& c) {
        coord_t v = (b - a) ^ (c - a);
        if(-eps <= v && v <= eps) {
            return 0;
        } else if(v > 0) {
            return 1;
        } else {
            return -1;
        }
    }

    friend bool point_on_segment(
        const Point& a, const Point& b, const Point& p
    ) {
        return ccw(a, b, p) == 0 && p.x >= min(a.x, b.x) - eps &&
               p.x <= max(a.x, b.x) + eps && p.y >= min(a.y, b.y) - eps &&
               p.y <= max(a.y, b.y) + eps;
    }

    friend bool point_in_triangle(
        const Point& a, const Point& b, const Point& c, const Point& p
    ) {
        int d1 = ccw(a, b, p);
        int d2 = ccw(b, c, p);
        int d3 = ccw(c, a, p);
        return (d1 >= 0 && d2 >= 0 && d3 >= 0) ||
               (d1 <= 0 && d2 <= 0 && d3 <= 0);
    }

    friend Point line_line_intersection(
        const Point& a1, const Point& b1, const Point& a2, const Point& b2
    ) {
        return a1 +
               (b1 - a1) * ((a2 - a1) ^ (b2 - a2)) / ((b1 - a1) ^ (b2 - a2));
    }

    friend bool collinear(const Point& a, const Point& b) {
        return abs(a ^ b) < eps;
    }

    friend Point circumcenter(const Point& a, const Point& b, const Point& c) {
        Point mid_ab = (a + b) / 2.0;
        Point mid_ac = (a + c) / 2.0;
        Point perp_ab = (b - a).perp();
        Point perp_ac = (c - a).perp();
        return line_line_intersection(
            mid_ab, mid_ab + perp_ab, mid_ac, mid_ac + perp_ac
        );
    }
};

class VoronoiDiagram {
  private:
    static constexpr coord_t INF = 1e100;
    static inline coord_t sweep_x;

    struct Arc {
        mutable Point p, q;
        mutable int id = 0, i;

        Arc(const Point& p, const Point& q, int i) : p(p), q(q), i(i) {}

        coord_t get_y(coord_t x) const {
            if(q.y == INF) {
                return INF;
            }
            x += Point::eps;
            Point mid = (p + q) / 2.0;
            Point dir = (p - mid).perp();
            coord_t D = (x - p.x) * (x - q.x);
            if(D < 0) {
                return -INF;
            }

            if(abs(dir.y) < Point::eps) {
                return (x < mid.x) ? -INF : INF;
            }

            return mid.y +
                   ((mid.x - x) * dir.x + sqrtl(D) * dir.norm()) / dir.y;
        }

        bool operator<(const coord_t& y) const { return get_y(sweep_x) < y; }

        bool operator<(const Arc& o) const {
            return get_y(sweep_x) < o.get_y(sweep_x);
        }
    };

    using Beach = multiset<Arc, less<>>;

    struct Event {
        coord_t x;
        int id;
        Beach::iterator it;

        Event(coord_t x, int id, Beach::iterator it) : x(x), id(id), it(it) {}

        bool operator<(const Event& e) const { return x > e.x; }
    };

    Beach beach_line;
    vector<pair<Point, int>> vertices;
    priority_queue<Event> event_queue;
    vector<pair<int, int>> edges;
    vector<bool> valid;
    int n, next_vertex_id;

    void update_vertex_event(Beach::iterator it) {
        if(it->i == -1) {
            return;
        }

        valid[-it->id] = false;
        auto prev_it = prev(it);

        if(collinear(it->q - it->p, prev_it->p - it->p)) {
            return;
        }

        it->id = --next_vertex_id;
        valid.push_back(true);

        Point center = circumcenter(it->p, it->q, prev_it->p);
        coord_t event_x = center.x + (center - it->p).norm();

        bool valid_event =
            event_x > sweep_x - Point::eps &&
            prev_it->get_y(event_x) + Point::eps > it->get_y(event_x);
        if(valid_event) {
            event_queue.push(Event(event_x, it->id, it));
        }
    }

    void add_edge(int i, int j) {
        if(i == -1 || j == -1) {
            return;
        }
        edges.push_back({vertices[i].second, vertices[j].second});
    }

    void add_point(int i) {
        Point p = vertices[i].first;

        auto split_it = beach_line.lower_bound(p.y);
        auto new_it = beach_line.insert(split_it, Arc(p, split_it->p, i));
        auto prev_it =
            beach_line.insert(new_it, Arc(split_it->p, p, split_it->i));

        add_edge(i, split_it->i);

        update_vertex_event(prev_it);
        update_vertex_event(new_it);
        update_vertex_event(split_it);
    }

    void remove_arc(Beach::iterator it) {
        auto prev_it = prev(it);
        auto next_it = next(it);

        beach_line.erase(it);
        prev_it->q = next_it->p;

        add_edge(prev_it->i, next_it->i);

        update_vertex_event(prev_it);
        update_vertex_event(next_it);
    }

  public:
    VoronoiDiagram(const vector<Point>& points, bool fix_coordinates = true) {
        n = points.size();
        vertices.resize(n);

        for(int i = 0; i < n; i++) {
            vertices[i] = {points[i], i};
        }

        if(fix_coordinates && n > 0) {
            // Rotate around center by 1.0 radians.
            for(int i = 0; i < n; i++) {
                vertices[i].first = vertices[i].first.rotate(1.0);
            }
        }

        sort(vertices.begin(), vertices.end());
    }

    vector<pair<int, int>> compute(coord_t X = 1e9) {
        edges.clear();
        beach_line.clear();
        event_queue = priority_queue<Event>();

        X *= 3;
        beach_line.insert(Arc(Point(-X, -X), Point(-X, X), -1));
        beach_line.insert(Arc(Point(-X, X), Point(INF, INF), -1));

        for(int i = 0; i < n; i++) {
            event_queue.push(Event(vertices[i].first.x, i, beach_line.end()));
        }

        next_vertex_id = 0;
        valid.assign(1, false);

        while(!event_queue.empty()) {
            Event e = event_queue.top();
            event_queue.pop();
            sweep_x = e.x;

            if(e.id >= 0) {
                add_point(e.id);
            } else if(valid[-e.id]) {
                remove_arc(e.it);
            }
        }

        return edges;
    }

    const vector<pair<int, int>>& get_edges() const { return edges; }
};

class DSU {
  public:
    int n;
    vector<int> par;
    vector<int> sz;

    DSU(int _n = 0) { init(_n); }

    void init(int _n) {
        n = _n;
        par.assign(n + 1, 0);
        sz.assign(n + 1, 0);
        for(int i = 0; i <= n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int root(int u) { return par[u] = ((u == par[u]) ? u : root(par[u])); }
    bool connected(int x, int y) { return root(x) == root(y); }

    int unite(int x, int y) {
        x = root(x), y = root(y);
        if(x == y) {
            return x;
        }
        if(sz[x] > sz[y]) {
            swap(x, y);
        }
        par[x] = y;
        sz[y] += sz[x];
        return y;
    }

    vector<vector<int>> components() {
        vector<vector<int>> comp(n + 1);
        for(int i = 0; i <= n; i++) {
            comp[root(i)].push_back(i);
        }
        return comp;
    }
};

int n, q;
vector<Point> pnts;
vector<pair<int, int>> queries;

void read() {
    cin >> n;
    pnts.resize(n);
    for(auto& p: pnts) {
        cin >> p.x >> p.y;
    }

    cin >> q;
    queries.resize(q);
    for(auto& query: queries) {
        cin >> query;
        query.first--;
        query.second--;
    }
}

void solve() {
    // The key to this problem is that we need to build the Euclidean spanning
    // tree, and then the problem ends up being computing the largest edge
    // between the two endpoints. This can be done in different ways, easiest
    // probably being parallel binary search as part of the Kruskal which we
    // anyways need to do. One corner case that isn't well described in the
    // problem statement is s[i] = t[i], where the answer should be 0.0.

    auto voronoi = VoronoiDiagram(pnts);
    auto edges = voronoi.compute();

    sort(
        edges.begin(), edges.end(),
        [&](pair<int, int> edge1, pair<int, int> edge2) {
            return (pnts[edge1.first] - pnts[edge1.second]).norm2() <
                   (pnts[edge2.first] - pnts[edge2.second]).norm2();
        }
    );

    vector<int> low(q, 0), high(q, edges.size() - 1);
    while(true) {
        bool has_queries = false;
        vector<vector<int>> queries_at_pos(edges.size());
        for(int i = 0; i < q; i++) {
            if(low[i] <= high[i]) {
                has_queries = true;

                int mid = (low[i] + high[i]) / 2;
                queries_at_pos[mid].push_back(i);
            }
        }

        if(!has_queries) {
            break;
        }

        DSU dsu(n);
        for(int i = 0; i < (int)edges.size(); i++) {
            dsu.unite(edges[i].first, edges[i].second);

            for(int query: queries_at_pos[i]) {
                if(dsu.connected(queries[query].first, queries[query].second)) {
                    high[query] = i - 1;
                } else {
                    low[query] = i + 1;
                }
            }
        }
    }

    for(int i = 0; i < q; i++) {
        if(queries[i].first == queries[i].second) {
            cout << setprecision(10) << fixed << 0.0 << endl;
        } else {
            auto edge = edges[high[i] + 1];
            cout << setprecision(10) << fixed
                 << (pnts[edge.first] - pnts[edge.second]).norm() << endl;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 4) Python solution with detailed comments

Below is a Python implementation that follows the same high-level idea, but it does **not implement a full Voronoi diagram** (too long/complex in Python here). Instead, it uses a Delaunay triangulation from `scipy.spatial` if available. If not allowed in your environment, you would need to port a triangulation algorithm; conceptually it's the same after you get triangulation edges.

If external libraries are not allowed on the judge, you must re-implement Delaunay/Voronoi in Python, which is quite lengthy. Here, I'll assume we can use `scipy`.

```python
import sys
import math
from collections import defaultdict

# NOTE: This version uses scipy.spatial.Delaunay to obtain the Delaunay
# triangulation and extract edges, then does the same parallel binary search
# on these edges. On an online judge without scipy this would not run.

try:
    from scipy.spatial import Delaunay
except ImportError:
    Delaunay = None  # placeholder, see note above


def read_ints():
    return list(map(int, sys.stdin.readline().split()))


class DSU:
    """Disjoint Set Union / Union-Find with path compression and union by size."""
    def __init__(self, n):
        self.par = list(range(n))  # parent array
        self.sz = [1] * n          # size array

    def root(self, x):
        """Find the representative (root) of x with path compression."""
        if self.par[x] != x:
            self.par[x] = self.root(self.par[x])
        return self.par[x]

    def unite(self, a, b):
        """Union the sets containing a and b."""
        a = self.root(a)
        b = self.root(b)
        if a == b:
            return a
        # union by size
        if self.sz[a] > self.sz[b]:
            a, b = b, a
        self.par[a] = b
        self.sz[b] += self.sz[a]
        return b

    def connected(self, a, b):
        """Check if a and b are in the same component."""
        return self.root(a) == self.root(b)


def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)

    n = int(next(it))
    points = []
    for _ in range(n):
        x = float(next(it))
        y = float(next(it))
        points.append((x, y))

    q = int(next(it))
    queries = []
    for _ in range(q):
        s = int(next(it)) - 1  # to 0-based
        t = int(next(it)) - 1
        queries.append((s, t))

    # Handle small / degenerate cases quickly
    if n <= 1:
        # Only one or zero oases; answer is always 0
        out = []
        for s, t in queries:
            out.append("0.0000000000")
        sys.stdout.write("\n".join(out))
        return

    if Delaunay is None:
        raise RuntimeError("Delaunay triangulation (scipy) not available.")

    # Build Delaunay triangulation: this is a triangulation of the convex hull
    # That gives us all edges used by the Euclidean MST.
    coords = points  # list of (x, y)
    tri = Delaunay(coords)

    # Extract edges from Delaunay triangles.
    # Each simplex is a triangle [i, j, k]; all edges (i,j), (j,k), (k,i) are present.
    edge_set = set()
    for simplex in tri.simplices:
        i, j, k = simplex
        if i > j:
            i, j = j, i
        if j > k:
            j, k = k, j
        if i > j:
            i, j = j, i
        # Add the three undirected edges (i,j), (j,k), (i,k)
        edge_set.add((i, j))
        edge_set.add(tuple(sorted((j, k))))
        edge_set.add(tuple(sorted((i, k))))

    edges = list(edge_set)

    # Sort edges by squared Euclidean distance
    def sqdist(e):
        u, v = e
        dx = coords[u][0] - coords[v][0]
        dy = coords[u][1] - coords[v][1]
        return dx * dx + dy * dy

    edges.sort(key=sqdist)
    m = len(edges)

    # Prepare parallel binary search ranges
    low = [0] * q
    high = [m - 1] * q

    # Precompute which queries have s == t (answer = 0)
    same_node = [queries[i][0] == queries[i][1] for i in range(q)]

    while True:
        has_queries = False
        queries_at_pos = [[] for _ in range(m)]

        # Assign each active query an edge index = current mid
        for i in range(q):
            if same_node[i]:
                # This query's answer is 0, no need to refine
                continue
            if low[i] <= high[i]:
                has_queries = True
                mid = (low[i] + high[i]) // 2
                queries_at_pos[mid].append(i)

        if not has_queries:
            break

        # DSU on [0..n-1]
        dsu = DSU(n)

        # Sweep edges from smallest to largest
        for ei in range(m):
            u, v = edges[ei]
            dsu.unite(u, v)

            # Process queries that are checking this mid index
            for qi in queries_at_pos[ei]:
                s, t = queries[qi]
                if dsu.connected(s, t):
                    # If s and t are connected with edges [0..ei], answer index <= ei
                    high[qi] = ei - 1
                else:
                    # Still disconnected, answer index > ei
                    low[qi] = ei + 1

    # Now low[i] == high[i] + 1 for non-degenerate queries.
    # The first index where s and t become connected is pos = high[i] + 1.
    out_lines = []
    for i in range(q):
        if same_node[i]:
            # s == t
            out_lines.append(f"{0.0:.10f}")
        else:
            pos = high[i] + 1
            u, v = edges[pos]
            dx = coords[u][0] - coords[v][0]
            dy = coords[u][1] - coords[v][1]
            dist = math.hypot(dx, dy)
            out_lines.append(f"{dist:.10f}")

    sys.stdout.write("\n".join(out_lines))


if __name__ == "__main__":
    main()
```

**Important note:**
If you need a pure-standard-library Python solution for a judge, you must implement (or port) a Delaunay triangulation or Voronoi-based method like the C++ code does. The rest of the approach (sorting edges, DSU, parallel binary search) stays essentially the same.

---

## 5) Compressed editorial

- The caravan chooses routes that minimize its maximum time outside oases, i.e., minimize the maximum segment length along the path.
- Model all oases as vertices of a complete Euclidean graph (weight = distance). For a path, define its bottleneck as the max edge weight.
- For any two nodes `s, t`, the minimal possible bottleneck over all `s-t` paths is exactly the maximum edge on the **unique** `s-t` path in a **minimum spanning tree** (MST) of the graph (minimax/MST property).
- The Euclidean MST is a subgraph of the **Delaunay triangulation**. So if we compute the Delaunay triangulation (via Voronoi diagram), we only need to consider those edges for MST, not all `O(n^2)` pairs.
- The code uses a custom Voronoi implementation (`VoronoiDiagram`) to get all pairs of points whose Voronoi cells share an edge, which are exactly Delaunay edges.
- These edges are sorted by squared length. Instead of explicitly building the MST tree and running LCA, the solution uses **parallel binary search** over the edge list:
  - For each query, we binary search the smallest edge index `k` such that `s` and `t` become connected if we union edges `0..k` in that order.
  - Each binary search step is done for all queries simultaneously in `O(|E| + q)` time by:
    - Resetting DSU.
    - Sweeping edges in increasing index, uniting endpoints.
    - At each index `i`, answering connectivity for all queries whose current mid = `i` and narrowing their [low, high] range.
  - Complexity: `O((|E| + q) log |E|)` DSU operations.
- Finally, for query `i`, the minimal bottleneck distance is the length of `edges[pos_i]`, where `pos_i = high[i] + 1` after the search. If `s_i == t_i`, answer is `0.0`.
