思路:最小生成树

按照题意由于数据只有1000，那么直接建造一个无向完全图，无向完全图的边数为$n*(n-1)/2$，要求图联通，直接跑最小生成树即可. $\\$ 整体时间复杂度$o(n^2*log_2n)$$\\$ 还有一个很好想到的思路，直接二分答案然后把符合的边加入到集合之中最后整体判断该图是不是联通图即可$\\$ 整体时间复杂度$o(n^2*{log_2}^2n)$ $\\$ 最小生成树->https://oi-wiki.org/graph/mst/

代码如下

$cpp$

#include <bits/stdc++.h>//最小生成树
using namespace std;
#define N 1005
#define int long long
int n;
pair<int, int>a[N];
struct node {
	int x, y, w;
} w[N*N];
int cnt;
bool cmp(node a, node b) {
	return a.w < b.w;
}
struct DSU {
	vector<int> fa, p, e, f;
	DSU(int n) {
		fa.resize(n + 1);
		iota(fa.begin(), fa.end(), 0);
		p.resize(n + 1, 1);
		e.resize(n + 1);
		f.resize(n + 1);
	}
	int get(int x) {
		while (x != fa[x]) {
			x = fa[x] = fa[fa[x]];
		}
		return x;
	}
	bool merge(int x, int y) { // 设x是y的祖先
		if (x == y) f[get(x)] = 1;
		x = get(x), y = get(y);
		e[x]++;
		if (x == y) return false;
		if (x < y) swap(x, y); // 将编号小的合并到大的上
		fa[y] = x;
		f[x] |= f[y], p[x] += p[y], e[x] += e[y];
		return true;
	}
	bool same(int x, int y) {
		return get(x) == get(y);
	}
	bool F(int x) { // 判断连通块内是否存在自环
		return f[get(x)];
	}
	int size(int x) { // 输出连通块中点的数量
		return p[get(x)];
	}
	int E(int x) { // 输出连通块中边的数量
		return e[get(x)];
	}
};
long long dis(pair<long long, long long> a, pair<long long, long long>b) {
	return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
int sqr(int x) {
	int l = 0, r = 1e9;
	while (l <= r) {
		int mid = (l + r) / 2;
		if ((mid * 2) * (mid * 2) >= x) {
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	return r + 1;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].first >> a[i].second;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			w[++cnt] = {i, j, dis(a[i], a[j])};
		}
	}
	sort(w + 1, w + 1 + cnt, cmp);
	int now = n;
	DSU dsu(n);
	for (int i = 1; i <= cnt; i++) {
		if (dsu.get(w[i].x) != dsu.get(w[i].y)) {
			dsu.merge(w[i].x, w[i].y);
			now--;
		}
		if (now == 1) {
			cout << sqr(w[i].w);
			break;
		}
	}
	return 0;
}

$cpp$

#include <bits/stdc++.h>//二分判断连通图
using namespace std;
#define N 1005
pair<long long, long long>a[N];
int n;
struct DSU {
	vector<int> fa, p, e, f;
	DSU(int n) {
		fa.resize(n + 1);
		iota(fa.begin(), fa.end(), 0);
		p.resize(n + 1, 1);
		e.resize(n + 1);
		f.resize(n + 1);
	}
	int get(int x) {
		while (x != fa[x]) {
			x = fa[x] = fa[fa[x]];
		}
		return x;
	}
	bool merge(int x, int y) { // 设x是y的祖先
		if (x == y) f[get(x)] = 1;
		x = get(x), y = get(y);
		e[x]++;
		if (x == y) return false;
		if (x < y) swap(x, y); // 将编号小的合并到大的上
		fa[y] = x;
		f[x] |= f[y], p[x] += p[y], e[x] += e[y];
		return true;
	}
	bool same(int x, int y) {
		return get(x) == get(y);
	}
	bool F(int x) { // 判断连通块内是否存在自环
		return f[get(x)];
	}
	int size(int x) { // 输出连通块中点的数量
		return p[get(x)];
	}
	int E(int x) { // 输出连通块中边的数量
		return e[get(x)];
	}
};
long long dis(pair<long long, long long> a, pair<long long, long long>b) {
	return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
bool check(long long x) {
	DSU dsu(n);
	x = (x * 2) * (x * 2);
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			if (dis(a[i], a[j]) <= x) {
				dsu.merge(i, j);
			}
		}
	}
	set<int>s;
	for (int i = 1; i <= n; i++) {
		s.insert(dsu.get(i));
	}
	if (s.size() == 1)
		return true;
	else
		return false;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].first >> a[i].second;
	}
	long long l = 0, r = 5e8;
	while (l <= r) {
		long long mid = (l + r) / 2;
		if (check(mid)) {
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	cout << r + 1 << '\n';
	return 0;
}

$python$

class DSU:
    def __init__(self, n):
        self.fa = list(range(n + 1))
        self.p = [1] * (n + 1)
        self.e = [0] * (n + 1)
        self.f = [0] * (n + 1)

    def get(self, x):
        if self.fa[x] != x:
            self.fa[x] = self.get(self.fa[x])
        return self.fa[x]

    def merge(self, x, y):
        if x == y:
            self.f[self.get(x)] = 1
        x = self.get(x)
        y = self.get(y)
        self.e[x] += 1
        if x == y:
            return False
        if x < y:
            x, y = y, x
        self.fa[y] = x
        self.f[x] |= self.f[y]
        self.p[x] += self.p[y]
        self.e[x] += self.e[y]
        return True

    def same(self, x, y):
        return self.get(x) == self.get(y)

    def F(self, x):
        return self.f[self.get(x)]

    def size(self, x):
        return self.p[self.get(x)]

    def E(self, x):
        return self.e[self.get(x)]

def dis(a, b):
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2

def sqr(x):
    l, r = 0, int(1e9)
    while l <= r:
        mid = (l + r) // 2
        if (mid * 2) * (mid * 2) >= x:
            r = mid - 1
        else:
            l = mid + 1
    return r + 1

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    a = [(int(data[i * 2 + 1]), int(data[i * 2 + 2])) for i in range(n)]
    
    w = []
    cnt = 0
    
    for i in range(n):
        for j in range(i + 1, n):
            w.append((i + 1, j + 1, dis(a[i], a[j])))
            cnt += 1
    
    w.sort(key=lambda x: x[2])
    
    now = n
    dsu = DSU(n)
    
    for i in range(cnt):
        if dsu.get(w[i][0]) != dsu.get(w[i][1]):
            dsu.merge(w[i][0], w[i][1])
            now -= 1
        if now == 1:
            print(sqr(w[i][2]))
            break

if __name__ == "__main__":
    main()

$java$

import java.util.*;

class DSU {
    private int[] fa, p, e, f;

    public DSU(int n) {
        fa = new int[n + 1];
        p = new int[n + 1];
        e = new int[n + 1];
        f = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            fa[i] = i;
            p[i] = 1;
        }
    }

    public int get(int x) {
        if (fa[x] != x) {
            fa[x] = get(fa[x]);
        }
        return fa[x];
    }

    public boolean merge(int x, int y) {
        if (x == y) {
            f[get(x)] = 1;
        }
        x = get(x);
        y = get(y);
        e[x]++;
        if (x == y) {
            return false;
        }
        if (x < y) {
            int temp = x;
            x = y;
            y = temp;
        }
        fa[y] = x;
        f[x] |= f[y];
        p[x] += p[y];
        e[x] += e[y];
        return true;
    }

    public boolean same(int x, int y) {
        return get(x) == get(y);
    }

    public boolean F(int x) {
        return f[get(x)] == 1;
    }

    public int size(int x) {
        return p[get(x)];
    }

    public int E(int x) {
        return e[get(x)];
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Pair[] a = new Pair[n + 1];

        for (int i = 1; i <= n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            a[i] = new Pair(x, y);
        }

        List<Node> w = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                w.add(new Node(i, j, dis(a[i], a[j])));
            }
        }

        Collections.sort(w, Comparator.comparingLong(node -> node.w));

        int now = n;
        DSU dsu = new DSU(n);
        for (Node node : w) {
            if (dsu.get(node.x) != dsu.get(node.y)) {
                dsu.merge(node.x, node.y);
                now--;
            }
            if (now == 1) {
                System.out.println(sqr(node.w));
                break;
            }
        }
    }

    static long dis(Pair a, Pair b) {
        long dx = a.x - b.x;
        long dy = a.y - b.y;
        return dx * dx + dy * dy;
    }

    static int sqr(long x) {
        int l = 0, r = (int) 1e9;
        while (l <= r) {
            int mid = (l + r) / 2;
            if ((mid * 2L) * (mid * 2L) >= x) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return r + 1;
    }
}

class Node {
    int x, y;
    long w;

    Node(int x, int y, long w) {
        this.x = x;
        this.y = y;
        this.w = w;
    }
}

class Pair {
    int x, y;

    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

题目内容

塔之国有$n$个城市，塔塔作为塔之国国王，他希望所有塔之国的城市能够连通起来。

现在他下令塔之国的所有施工队同时施工同时，已知塔之国的施工队的施工速度均为$1$距离单位/年，

对于每个城市，城市的领导者都会向每个相邻的城市派出施工队进行修路(所有城市相邻)，

并且每个施工队都按照最短的路线修路，如果两个施工队碰头，那么两个城市相连。

现在给你$n$个城市的坐标，塔塔想知道塔之国的城市最少需要多少年才能全部连通(城市$A$和城市$B$连通，当且仅当$A$到$B$有一条通只路)。

输入描述

第一行一个整数$n(1≤n≤1000)$，表示城市数量。

接下来$n$行每行两个整数$x_i(-10^8 ≤x_i≤ 10^8 ),y_i(-10^8 ≤y_i≤ 10^8 )$

用空格分隔，表示城市的坐标。

输出描述

输出仅有一个整数，表示城市相连需要的年数向上取整的结果。

例如，如果需要$2.5$年可以连通，请输出$3$，如果如要$4$年可以连通，请输出$4$。

样例1

输入

3
0 0
0 5
6 0

输出

3

说明

当$(6,0)$和$(0,0)$连在一起时，所有城市连在一起，此时需要$3$年。

样例2

输入

2
0 0
1 0

输出

1

说明

初始不连通，$0.5$年可以连通，向上取整得到$1$。