#include #include #include #include #include using namespace std; #define MAX 2e9; vector >P; int N; struct UnionFind { vector par; vector sizes; UnionFind(int n) : par(n), sizes(n, 1) { for (int i = 0; i < n; i++) par[i] = i; } int find(int x) { if (x == par[x])return x; return par[x] = find(par[x]); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (sizes[x] < sizes[y]) swap(x, y); par[y] = x; sizes[x] += sizes[y]; } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return sizes[find(x)]; } }; struct Edge { int a, b; long long cost; bool operator<(const Edge& o) const { return cost < o.cost; } }; struct Graph { vector es; bool kruskal(int d) { bool flag = true; sort(es.begin(), es.end()); UnionFind uf(N); for (int ei = 0; ei < es.size(); ei++) { Edge& e = es[ei]; if (!uf.same(e.a, e.b)) { if (e.cost > (long long)d*d) { flag = false; break; } uf.unite(e.a, e.b); if (uf.same(0, N - 1)) break; } } return flag; } }; Graph input_graph() { Graph g; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { Edge e; e.a = i; e.b = j; e.cost = (P[i].first - P[j].first)*(P[i].first - P[j].first) + (P[i].second - P[j].second)*(P[i].second - P[j].second); cout << e.cost << endl; g.es.push_back(e); } } return g; } int main() { cin >> N; P.resize(N); for (int i = 0; i < N; i++) { int x, y; cin >> x >> y; P[i] = make_pair(x, y); } Graph g = input_graph(); long long left = 0; long long right = MAX; int mid; while (left < right) { mid = (left + right) / 2; if (g.kruskal(mid)) { right = mid; } else { left = mid+1; } } cout << (int)ceil(mid/10.) * 10 << endl; return 0; }