#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namespace std; typedef long long int ll; #define REP(i,n) for(int i=0; i=0; --i) #define FOR(i,a,n) for(int i=a; i=a; --i) #define VDOUT(x) cerr << #x << "\n";for(auto i : x ) cerr << " " << i << "\n"; #define DOUT(x) cerr << #x << " = " << x << "\n"; #define COUT(x) cout << x << "\n"; #define COUT2(x,y) cout < uni_; h_int Root(h_int a) { if (uni_[a] < 0) return a; return uni_[a] = Root(uni_[a]); } public: UnionFind(h_int max_n) { uni_.resize(max_n, -1); } bool Connect(h_int a, h_int b) { a = Root(a); b = Root(b); if (a == b) return false; if (uni_[a] > uni_[b]) std::swap(a, b); uni_[a] += uni_[b]; uni_[b] = a; return true; } bool Same(h_int a, h_int b) { return Root(a) == Root(b); } h_int CountRoot() { h_int cnt = 0; for (auto i : uni_) { if (i < 0) ++cnt; } return cnt; } }; struct Vector { h_int x_; h_int y_; Vector() :x_(0), y_(0) {} Vector(h_int x, h_int y) :x_(x), y_(y) {} h_int GetDistance(const Vector& v) { return (x_ - v.x_)*(x_ - v.x_) + (y_ - v.y_)*(y_ - v.y_); } }; vector> dis; bool Solve(h_int x) { x *= 10; UnionFind uni(dis.size()); REP(i, dis.size()) { FOR(j, i + 1, dis.size()) { if (dis[i][j] <= x*x) { uni.Connect(i, j); } } } // DOUT(x); // DOUT(uni.CountRoot()); return uni.Same(0, dis.size() - 1); } signed main() { INI; vector v; h_int n; cin >> n; v.resize(n); REP(i, n) { h_int x, y; cin >> x >> y; v[i] = Vector(x, y); } REP(i, n) { vector tmp; REP(j, n) { if (i > j) { tmp.push_back(dis[j][i]); } else if (i == j) { tmp.push_back(0); } else { tmp.push_back(v[i].GetDistance(v[j])); } } dis.push_back(tmp); } h_int left=0; h_int right = 1000000000; while (abs(left - right) > 1) { h_int mid = (left + right) / 2; if (Solve(mid)) { right = mid; } else { left = mid; } } COUT(right*10); return 0; }