#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair P; #define MOD 1000000007 // 10^9 + 7 #define INF 2000000000 // 10^9 #define LLINF 1LL<<60 class UF { private: std::vector parent; std::vector level; std::vector num_member; // 同じグループに属するメンバーの数 // 自身込み public: // コンストラクタ ※注意※ 0~nまでのn+1個を作る UF(int n) { for (int i = 0; i <= n; i++) { parent.push_back(i); // level.push_back(1); // 木の深さ num_member.push_back(1); } } // 木の根を求める int root(int x) { if (parent[x] == x)return x; else return parent[x] = root(parent[x]); } // 同じ集合に属するメンバーの数を求める int numOfmember(int x) { if (parent[x] == x) return num_member[x]; else return num_member[x] = numOfmember(parent[x]); } // xとyの属する集合を合併 void unite(int x, int y) { int rx = root(x); int ry = root(y); if (rx == ry) return; // 元々合併済みの場合 if (level[rx] < level[ry]) { num_member[ry] = numOfmember(ry) + numOfmember(rx); parent[rx] = ry; } else { num_member[rx] = numOfmember(ry) + numOfmember(rx); parent[ry] = rx; if (level[rx] == level[ry]) level[rx]++; } } // xとyが同じ集合に属するか否か bool same(int x, int y) { return root(x) == root(y); // rootが同じなら同じ集合に含まれる } }; ll X[1009], Y[1009]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; for (int i = 1; i <= N; i++) cin >> X[i] >> Y[i]; ll left = 0; ll right = INF; // left < ans <= right while (left +10 != right) { UF uf(N); ll mid = (left + right) / 2; mid = (mid / 10) * 10; for (int i = 1; i <= N; i++) { for (int j = i + 1; j <= N; j++) { ll dis = (X[i] - X[j])*(X[i] - X[j]) + (Y[i] - Y[j])*(Y[i] - Y[j]); if (mid*mid >= dis) uf.unite(i, j); } } if (uf.numOfmember(1) == N) right = mid; else left = mid; } cout << right << endl; return 0; }