#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 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define INIT std::ios::sync_with_stdio(false);std::cin.tie(0); // VAR(int, x); #define VAR(type, ...)type __VA_ARGS__;Scan(__VA_ARGS__); template void Scan(T& t) { std::cin >> t; } templatevoid Scan(First& first, Rest&...rest) { std::cin >> first; Scan(rest...); } #define OUT(d) std::cout<<(d); #define FOUT(n, d) std::cout< c(n);for(auto& i:c)std::cin>>i; #define MAT(type, c, m, n) std::vector> c(m, std::vector(n));for(auto& r:c)for(auto& i:r)std::cin>>i; #define ALL(a) (a).begin(),(a).end() #define FOR(i, a, b) for(int i=(a);i<(b);++i) #define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i) #define REP(i, n) for(int i=0;i=0;--i) #define PAIR std::pair #define IN(a, x, b) (a<=x && x<=b) #define IN2(a0, y, a1, b0, x, b1) (a0<=y && y(end-start).count();std::cerr<<"[Time:"< parent; std::vector height; public: UnionFind(int size) : parent(size), height(size, 0) { REP(i, size) { parent[i] = i; } } void init(int size) { parent.resize(size); height.resize(size, 0); REP(i, size) { parent[i] = i; } } int find(int x) { if (parent[x] == x) { return x; } return parent[x] = find(parent[x]); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (height[x] < height[y]) parent[x] = y; else parent[y] = x; if (height[x] == height[y]) ++height[x]; } bool same(int x, int y) { return find(x) == find(y); } }; signed main() { INIT; /** * yukicoder No.94 * 考案(Union-Find木) * (i番目の中継局をa[i]で表す) * 1) ∀i,j s.t. 1<=i,j<=n, i!=j に対して、 * distance(a[i], a[j])<=10 ならば a[i]とa[j]をUnion * →O(N^2 A(N)) * 2) ∀i,j s.t. 1<=i,j<=n, i!=j に対して、 * same(a[i], a[j])==true ならば max = std::max(max, distance(a[i], a[j])) * →O(N^2 A(N)) * 3) if(n==0) OUT(1)BR; * else OUT(max+2)BR; * →O(1) **/ VAR(int, n); std::vector rs(n); REP(i, n) { std::cin >> rs[i].first >> rs[i].second; } UnionFind uf(n); REP(i, n) { REP(j, n) { if (i == j) continue; if (dist(rs[i], rs[j]) <= 10.0) { uf.unite(i, j); } } } double max_dist = 0; REP(i, n) { REP(j, n) { if (i == j)continue; if (uf.same(i, j)) { max_dist = std::max(max_dist, dist(rs[i], rs[j])); } } } if (n == 0) { OUT(1)BR; } else { FOUT(10, max_dist + 2)BR; } return 0; }