#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define REP(i, n) for (int (i) = 0; (i) < (n); (i)++) #define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++) #define RREP(i, a) for(int (i) = (a)-1; (i) >= 0; (i)--) #define FORR(i, a, b) for(int (i) = (a)-1; (i) >= (b); (i)--) #define PI acos(-1.0) #define DEBUG(C) cout<< C < #define VII vector #define VL vector #define VLL vector #define VD vector #define VDD vector #define PII pair #define PDD pair #define PLL pair #define VPII vector #define ALL(a) (a).begin(), (a).end() #define SORT(a) sort(ALL(a)) #define REVERSE(a) reverse(ALL(a)) #define MP make_pair #define FORE(a, b) for (auto &&a:b) #define FIND(s, e) (s.find(e) != s.end()) #define EB emplace_back using namespace std; typedef long long LL; typedef unsigned long long ULL; const int INF = 1e9; const int MOD = INF+7; const LL LLINF = 1e18; /*** UnionFindクラス ***/ class UnionFind { private: //uni[i]<0ならばiが親,そうでなければfind(uni[i])が親 vector uni; //グループ数 int SIZE; public: UnionFind(int size) { //初期状態では全ノード-1に設定し,よってすべてが親 this->uni = vector(size, -1); this->SIZE = size; } UnionFind() {} //xの親を返す int find(int x) { //uni[x]<0なのでxは親 if (uni[x] < 0) return x; //uni[x]に親ノードを入れることで連続での探索時間の短縮 return uni[x] = find(uni[x]); } //xとyが同じグループならばtrue bool same(int x, int y) { //xとyの親が同じならば同じグループに属するといえる return find(x) == find(y); } //xとyがそれぞれ属するグループを併合 //併合処理を行ったならばtrueを返す //xとyがもともと同じグループならばfalseを返す bool unite(int x, int y) { x = find(x); y = find(y); if (x == y) return false; //木の深さが小さいノードから大きいノードへ辺をはる if (uni[x] > uni[y]) swap(x, y); //yのグループをxに足す uni[x] += uni[y]; //yの親をxとする uni[y] = x; this->SIZE--; return true; } //グループ数を返す int size() { return this->SIZE; } //xが属するグループのノード数を返す int size(int x) { return -uni[find(x)]; } }; #define X first #define Y second int N; vector xy; UnionFind uf; #define int LL signed main(void) { cin >> N; xy.resize(N); REP(i, N) { int x, y; scanf("%d%d", &x, &y); xy[i] = {x, y}; } uf = UnionFind(N); vector> cost; REP(i, N)FOR(j, i + 1, N) { auto a = xy[i]; auto b = xy[j]; LL dis = (a.X - b.X) * (a.X - b.X) + (a.Y - b.Y) * (a.Y - b.Y); cost.EB(make_tuple(dis, i, j)); } SORT(cost); LL ans = 0; REP(i, cost.size()) { LL dis; int ii, jj; tie(dis, ii, jj) = cost[i]; if (!uf.same(ii, jj)) { uf.unite(ii, jj); ans = max(ans, dis); } } ans = sqrt(ans); ans = ans + 10 - (ans % 10); cout << ans << endl; return 0; }