Connecting Wells
Source: codechef
Difficulty: 2275

Connecting Wells
In a vast desert, there are isolated water wells scattered across various locations on a grid. Each well serves a different village, and the village leaders have agreed to dig channels to connect all the wells, making water access easier across the desert. However, they’re unsure how long this network of channels will take to complete.
There are$N$wells, the$i$-th well located at coordinates$(X_i, Y_i)$.
There are$N$channels, one for each well. At time$0$, all channels have a length of$0$, and the$i$-th channel originates from the$i$-th well i.e.$(X_i, Y_i)$Every second, channels extend$1$unit outward from each well in the four cardinal directions (north, east, south, and west). When two expanding channels from different wells overlap or touch, the wells are considered connected.
Find the minimum time at which all wells become connected.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains one integer$N$— the number of wells.
The$i$-th of the next$N$lines contain$2$integers each -$X_i$and$Y_i$, the coordinates of the$i$-th well.
Output Format
For each test case, output on a new line the minimum time it will take connect all the wells.
Constraints$1 \le T \le 10^3$$1 \le N \le 2000$$1 \le X_i, Y_i \le 10^9$The sum of$N$over all test cases does not exceed$2000$.
Sample 1:
Explanation:
Test Case 1
: After$1$second, both the channels from the wells intersect. Hence,$1$is the answer.
Test Case 2
: After$1$second, the channels from the$2$wells. touch at$(1, 2)$or$(2, 1)$. Hence$1$is the answer.

Sample Input:
4
2
1 1
1 2
2
1 1
2 2
3
1 5
4 3
2 4
1
1 1

Sample Output:
1
1
2
0

C++ solution:
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define debug(ARG) cout << "[" << #ARG << "]: " << ARG << endl
#else
#define debug(ARG) 42
#endif

using llu = unsigned long long;
using lld = long long;

#define forr(i, a, b) for (int i = (a); i < (b); i++)
#define forn(i, n) forr(i, 0, n)
#define dforn(i, n) for (int i = (n - 1); i >= 0; i--)
#define vec vector
#define pr pair
#define fs first
#define sd second
#define ins insert
#define ers erase
#define pb push_back
#define all(n) begin(n), end(n)
#define cln(a) cout << a << '\n'
#define ce(a) cout << a << ' '
#define ln cout << '\n'

typedef pr<long long, long long> ii;
typedef vec<long long> vi;
typedef vec<vec<int>> Adj;
typedef vec<vec<ii>> WAdj;

const int tam = 2e3;
ii wells[tam];

lld dist(ii &p1, ii &p2)
{
  if (p1.first == p2.first)
    return (abs(p1.second - p2.second) + 1) / 2;
  if (p1.second == p2.second)
    return (abs(p1.first - p2.first) + 1) / 2;
  return max(abs(p1.first - p2.first), abs(p1.second - p2.second));
}

void solv()
{
  int n;
  cin >> n;
  forn(i, n)
  {
    lld x, y;
    cin >> x >> y;
    wells[i] = {x, y};
  }
  lld inf = 1e10;
  vi dst(n + 1, inf);
  bool vis[n] = {};
  dst[0] = 0;
  lld res = 0;
  forn(p, n)
  {
    int node = n;
    forn(i, n) if (dst[i] < dst[node] && !vis[i]) node = i;
    vis[node] = true;
    res = max(res, dst[node]);
    forn(i, n)
    {
      if (i == node)
        continue;
      if (!vis[i] && dst[i] > dist(wells[node], wells[i]))
      {
        dst[i] = dist(wells[node], wells[i]);
      }
    }
  }
  cln(res);
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  cin >> t;
  while (t--)
    solv();
  return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	var words []string
	for scanner.Scan() {
		words = append(words, scanner.Text())
	}

	idx := 0
	T, _ := strconv.Atoi(words[idx])
	idx++

	results := make([]int, 0, T)

	for t := 0; t < T; t++ {
		N, _ := strconv.Atoi(words[idx])
		idx++

		wells := make([][2]int, N)
		for i := 0; i < N; i++ {
			x, _ := strconv.Atoi(words[idx])
			y, _ := strconv.Atoi(words[idx+1])
			wells[i] = [2]int{x, y}
			idx += 2
		}

		if N == 1 {
			results = append(results, 0)
			continue
		}

		dist := make([]int, N)
		inMST := make([]bool, N)
		for i := 0; i < N; i++ {
			dist[i] = math.MaxInt32
		}
		dist[0] = 0
		maxCost := 0

		for i := 0; i < N; i++ {
			u := -1
			minDist := math.MaxInt32
			for j := 0; j < N; j++ {
				if !inMST[j] && dist[j] < minDist {
					minDist = dist[j]
					u = j
				}
			}

			if u == -1 {
				break
			}

			inMST[u] = true
			if dist[u] > maxCost {
				maxCost = dist[u]
			}

			for v := 0; v < N; v++ {
				if !inMST[v] {
					dx := abs(wells[u][0] - wells[v][0])
					dy := abs(wells[u][1] - wells[v][1])
					var cost int

					if wells[u][0] == wells[v][0] {
						cost = (dy + 1) / 2
					} else if wells[u][1] == wells[v][1] {
						cost = (dx + 1) / 2
					} else {
						cost = max(dx, dy)
					}

					if cost < dist[v] {
						dist[v] = cost
					}
				}
			}
		}

		results = append(results, maxCost)
	}

	for _, res := range results {
		fmt.Println(res)
	}
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    public static long fun(int n, long[][] mat) {
        long low = 0, high = (long) 1e9;
        long ans = 0;

        while (low <= high) {
            long mid = (low + high) / 2;

            // Check if all points can be connected with max time `mid`
            if (canConnect(n, mat, mid)) {
                ans = mid;
                high = mid - 1; // Try for smaller time
            } else {
                low = mid + 1; // Increase time
            }
        }

        return ans;
    }

    private static boolean canConnect(int n, long[][] mat, long maxTime) {
        DSU dsu = new DSU(n);

        for (int i = 0; i < n; i++) {
            long x1 = mat[i][0], y1 = mat[i][1];
            for (int j = i + 1; j < n; j++) {
                long x2 = mat[j][0], y2 = mat[j][1];

                long time = calculateTime(x1, y1, x2, y2);

                // If this edge can be used within the time `maxTime`
                if (time <= maxTime) {
                    dsu.join(i, j);
                }
            }
        }

        // Check if all points are connected
        return dsu.countConnectedComp() == 1;
    }

    private static long calculateTime(long x1, long y1, long x2, long y2) {
        if (x1 == x2) return (Math.abs(y2 - y1) + 1) / 2;
        else if (y1 == y2) return (Math.abs(x2 - x1) + 1) / 2;
        return Math.max(Math.abs(x2 - x1), Math.abs(y2 - y1));
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int t = Integer.parseInt(st.nextToken());
        while (t-- > 0) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            long[][] mat = new long[n][2];
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                mat[i][0] = Long.parseLong(st.nextToken());
                mat[i][1] = Long.parseLong(st.nextToken());
            }
            bw.write(fun(n, mat) + "\n");
        }

        br.close();
        bw.flush();
        bw.close();
    }
}

class DSU {
    int[] parArr;
    int[] rankArr;

    DSU(int n) {
        parArr = new int[n];
        rankArr = new int[n];
        for (int i = 0; i < n; i++) parArr[i] = i;
    }

    public void join(int node1, int node2) {
        int par1 = findParent(node1);
        int par2 = findParent(node2);

        if (par1 != par2) {
            if (rankArr[par1] > rankArr[par2]) {
                parArr[par2] = par1;
            } else if (rankArr[par1] < rankArr[par2]) {
                parArr[par1] = par2;
            } else {
                rankArr[par1]++;
                parArr[par2] = par1;
            }
        }
    }

    public int findParent(int node) {
        if (parArr[node] != node) {
            parArr[node] = findParent(parArr[node]);
        }
        return parArr[node];
    }

    public int countConnectedComp() {
        int count = 0;
        for (int i = 0; i < parArr.length; i++) {
            if (parArr[i] == i) count++;
        }
        return count;
    }
}

JavaScript solution:
/* -------------------------------------------------------- */
/*   ( The Authentic JS CodeBuff )
 ___ _                      _              _ 
 | _ ) |_  __ _ _ _ __ _ __| |_ __ ____ _ (_)
 | _ \ ' \/ _` | '_/ _` / _` \ V  V / _` || |
 |___/_||_\__,_|_| \__,_\__,_|\_/\_/\__,_|/ |
                                        |__/ 
 */
/* ---------------------------------------------------------   */
/*    Youtube: https://youtube.com/@code-with-Bharadwaj        */
/*    Github : https://github.com/Manu577228                  */
/* ----------------------------------------------------------- */

const V8Flags = [
    '--max-old-space-size=4096', '--max-semi-space-size=16', '--stack-size=65536', '--reclaim-unused-memory',
    '--gc-interval=100', '--expose-gc', '--gc-global', '--optimize-for-speed',
    '--always-opt', '--max-inlined-source-size=600', '--max-inlined-bytecode-size=600', '--turbo-inline-js-wasm-calls',
    '--turbo', '--turbo-optimizer', '--force-optimization', '--no-lazy',
    '--no-lazy-inner-functions', '--optimize-for-size', '--initial-heap-size=64', '--max-heap-size=192',
    '--use-strict', '--predictable', '--single-threaded-gc', '--no-inline-new',
    '--opt', '--no-lazy-deserialization', '--no-browser-globals', '--turbo-inline-array-builtins',
    '--fast-math', '--fuzzing', '--minor-mc', '--incremental-marking',
    '--concurrent-recompilation', '--stress-compaction', '--experimental-flush-embedded-blob-icache', '--experimental-value-unavailable'
];

if (V8Flags.length > 0) {
        process.execArgv.push('--v8-options=' + V8Flags.join(' '));
}

let inputBuffer = Buffer.allocUnsafe(1e7);
let inputIndex = 0,
        inputLength = 0;
let outputBuffer = Buffer.allocUnsafe(1e7);
let outputIndex = 0;

let fs = require('fs');
inputLength = fs.readSync(process.stdin.fd, inputBuffer, 0, inputBuffer.length, null);

let readInt = () => {
        let n = 0;
        while (inputBuffer[inputIndex] < 48) inputIndex++;
        while (inputIndex < inputLength && inputBuffer[inputIndex] >= 48 && inputBuffer[inputIndex] <= 57) {
                n = n * 10 + (inputBuffer[inputIndex++] - 48);
        }
        return n;
};

let writeInt = (v, isLast = false) => {
        let d = [];
        do {
                d.push(v % 10);
                v = Math.floor(v / 10);
        } while (v > 0);
        for (let i = d.length - 1; i >= 0; i--) {
                outputBuffer[outputIndex++] = 48 + d[i];
        }
        if (isLast) outputBuffer[outputIndex++] = 10;
        else outputBuffer[outputIndex++] = 32;
};

let t = readInt();
while (t--) {
        let n = readInt();
        let w = Array(n).fill().map(() => ({
                x: readInt(),
                y: readInt()
        }));
        
        if (n === 1) {
                writeInt(0, true);
                continue;
        }
        
        let d = new Array(n).fill(Number.MAX_SAFE_INTEGER);
        let v = new Array(n).fill(false);
        d[0] = 0;
        let a = 0;
        
        for (let _ = 0; _ < n; _++) {
                let u = -1;
                let b = Number.MAX_SAFE_INTEGER;
                
                for (let i = 0; i < n; i++) {
                        if (!v[i] && d[i] < b) {
                                b = d[i];
                                u = i;
                        }
                }
                
                v[u] = true;
                a = Math.max(a, d[u]);
                
                for (let j = 0; j < n; j++) {
                        if (!v[j]) {
                                let dx = Math.abs(w[u].x - w[j].x);
                                let dy = Math.abs(w[u].y - w[j].y);
                                let c;
                                
                                if (w[u].x === w[j].x) c = Math.floor((dy + 1) / 2);
                                else if (w[u].y === w[j].y) c = Math.floor((dx + 1) / 2);
                                else c = Math.max(dx, dy);
                                
                                if (c < d[j]) d[j] = c;
                        }
                }
        }
        writeInt(a, true);
}

fs.writeSync(process.stdout.fd, outputBuffer.slice(0, outputIndex));

Python solution:
# cook your dish here
import sys
import math

def main():
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    T = int(data[idx])
    idx += 1
    results = []
    
    for _ in range(T):
        N = int(data[idx])
        idx += 1
        
        wells = []
        for _ in range(N):
            x, y = int(data[idx]), int(data[idx+1])
            wells.append((x, y))
            idx += 2
        
        if N == 1:
            results.append(0)
            continue
        
        # Use Prim's MST algorithm in O(N^2)
        dist = [float('inf')] * N
        inMST = [False] * N
        dist[0] = 0
        max_cost = 0

        for _ in range(N):
            u = -1
            best = float('inf')
            for i in range(N):
                if not inMST[i] and dist[i] < best:
                    best = dist[i]
                    u = i
            
            inMST[u] = True
            max_cost = max(max_cost, dist[u])

            for v in range(N):
                if not inMST[v]:
                    dx = abs(wells[u][0] - wells[v][0])
                    dy = abs(wells[u][1] - wells[v][1])
                    cost = 0

                    if wells[u][0] == wells[v][0]:  # same X
                        cost = (dy + 1) // 2
                    elif wells[u][1] == wells[v][1]:  # same Y
                        cost = (dx + 1) // 2
                    else:
                        cost = max(dx, dy)

                    if cost < dist[v]:
                        dist[v] = cost

        results.append(max_cost)
    
    for res in results:
        print(res)

if __name__ == "__main__":
    main()

Ruby solution:
def main
  input = $stdin.read.split
  idx = 0
  test_cases = input[idx].to_i
  idx += 1
  results = []

  test_cases.times do
    num_wells = input[idx].to_i
    idx += 1
    wells = []
    num_wells.times do
      x = input[idx].to_i
      y = input[idx + 1].to_i
      wells << [x, y]
      idx += 2
    end

    if num_wells == 1
      results << 0
      next
    end

    # Prim's algorithm
    dist = Array.new(num_wells, Float::INFINITY)
    in_mst = Array.new(num_wells, false)
    dist[0] = 0
    max_cost = 0

    num_wells.times do
      u = -1
      best = Float::INFINITY
      (0...num_wells).each do |i|
        if !in_mst[i] && dist[i] < best
          best = dist[i]
          u = i
        end
      end

      in_mst[u] = true
      max_cost = [max_cost, dist[u]].max

      (0...num_wells).each do |v|
        next if in_mst[v]

        dx = (wells[u][0] - wells[v][0]).abs
        dy = (wells[u][1] - wells[v][1]).abs
        cost = if wells[u][0] == wells[v][0]
                 (dy + 1) / 2
               elsif wells[u][1] == wells[v][1]
                 (dx + 1) / 2
               else
                 [dx, dy].max
               end

        if cost < dist[v]
          dist[v] = cost
        end
      end
    end

    results << max_cost
  end

  results.each { |res| puts res }
end

main