#line 1 "No_96_\u570f\u5916\u3067\u3059.cpp" #define YRSD #line 2 "YRS/all.hpp" #line 2 "YRS/aa/head.hpp" #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 TE template #define TES template #define Z auto #define ep emplace_back #define eb emplace #define fi first #define se second #define all(x) (x).begin(), (x).end() #define OV4(a, b, c, d, e, ...) e #define FOR1(a) for (int _ = 0; _ < (a); ++_) #define FOR2(i, a) for (int i = 0; i < (a); ++i) #define FOR3(i, a, b) for (int i = (a); i < (b); ++i) #define FOR4(i, a, b, c) for (int i = (a); i < (b); i += (c)) #define FOR(...) OV4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__) #define FOR1_R(a) for (int _ = (a) - 1; _ >= 0; --_) #define FOR2_R(i, a) for (int i = (a) - 1; i >= 0; --i) #define FOR3_R(i, a, b) for (int i = (b) - 1; i >= (a); --i) #define FOR4_R(i, a, b, c) for (int i = (b) - 1; i >= (a); i -= (c)) #define FOR_R(...) OV4(__VA_ARGS__, FOR4_R, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__) #define FOR_subset(t, s) for (int t = (s); t > -1; t = (t == 0 ? -1 : (t - 1) & s)) #define sort ranges::sort using namespace std; TE using vc = vector; TE using vvc = vc>; TE using T1 = tuple; TE using T2 = tuple; TE using T3 = tuple; TE using T4 = tuple; TE using max_heap = priority_queue; TE using min_heap = priority_queue, greater>; using u8 = unsigned char; using uint = unsigned int; using ll = long long; using ull = unsigned long long; using ld = long double; using i128 = __int128; using u128 = __uint128_t; using f128 = __float128; using u16 = uint16_t; using PII = pair; using PLL = pair; #ifdef YRSD constexpr bool dbg = 1; #else constexpr bool dbg = 0; #endif #line 2 "YRS/IO/IO.hpp" istream &operator>>(istream &I, i128 &x) { static string s; I >> s; int f = s[0] == '-'; x = 0; const int N = (int)s.size(); FOR(i, f, N) x = x * 10 + s[i] - '0'; if (f) x = -x; return I; } ostream &operator<<(ostream &O, i128 x) { static string s; s.clear(); bool f = x < 0; if (f) x = -x; while (x) s += '0' + x % 10, x /= 10; if (s.empty()) s += '0'; if (f) s += '-'; reverse(all(s)); return O << s; } istream &operator>>(istream &I, f128 &x) { static string s; I >> s, x = stold(s); return I; } ostream &operator<<(ostream &O, const f128 x) { return O << ld(x); } template istream &operator>>(istream &I, tuple &t) { return apply([&I](Z &...s) { ((I >> s), ...); }, t), I; } template istream &operator>>(istream &I, pair &x) { return I >> x.fi >> x.se; } template ostream &operator<<(ostream &O, const pair &x) { return O << x.fi << ' ' << x.se; } TE requires requires(T &c) { begin(c); end(c); } and (not is_same_v, string>) istream &operator>>(istream &I, T &c) { for (Z &e : c) I >> e; return I; } TE requires requires(const T &c) { begin(c); end(c); } and (not is_same_v, const char*>) and (not is_same_v, string>) and (not is_array_v> or not is_same_v>, char>) ostream &operator<<(ostream &O, const T &a) { if (a.empty()) return O; Z i = a.begin(); O << *i++; for (; i != a.end(); ++i) O << ' ' << *i; return O; } void IN() {} TE void IN(T &x, Z &...s) { cin >> x, IN(s...); } void print() { cout << '\n'; } TES void print(T &&x, S &&...y) { cout << x; if constexpr (sizeof...(S)) cout << ' '; print(forward(y)...); } void put() { cout << ' '; } TES void put(T &&x, S &&...y) { cout << x; if constexpr (sizeof...(S)) cout << ' '; put(forward(y)...); } #define INT(...) int __VA_ARGS__; IN(__VA_ARGS__) #define UINT(...) uint __VA_ARGS__; IN(__VA_ARGS__) #define LL(...) ll __VA_ARGS__; IN(__VA_ARGS__) #define ULL(...) ull __VA_ARGS__; IN(__VA_ARGS__) #define I128(...) i128 __VA_ARGS__; IN(__VA_ARGS__) #define STR(...) string __VA_ARGS__; IN(__VA_ARGS__) #define CH(...) char __VA_ARGS__; IN(__VA_ARGS__) #define REAL(...) re __VA_ARGS__; IN(__VA_ARGS__) #define VEC(T, a, n) vc a(n); IN(a) void YES(bool o = 1) { print(o ? "YES" : "NO"); } void Yes(bool o = 1) { print(o ? "Yes" : "No"); } void yes(bool o = 1) { print(o ? "yes" : "no"); } void NO(bool o = 1) { YES(not o); } void No(bool o = 1) { Yes(not o); } void no(bool o = 1) { yes(not o); } void ALICE(bool o = 1) { print(o ? "ALICE" : "BOB"); } void Alice(bool o = 1) { print(o ? "Alice" : "Bob"); } void alice(bool o = 1) { print(o ? "alice" : "bob"); } void BOB(bool o = 1) { ALICE(not o); } void Bob(bool o = 1) { Alice(not o); } void bob(bool o = 1) { alice(not o); } void POSSIBLE(bool o = 1) { print(o ? "POSSIBLE" : "IMPOSSIBLE"); } void Possible(bool o = 1) { print(o ? "Possible" : "Impossible"); } void possible(bool o = 1) { print(o ? "possible" : "impossible"); } void IMPOSSIBLE(bool o = 1) { POSSIBLE(not o); } void Impossible(bool o = 1) { Possible(not o); } void impossible(bool o = 1) { possible(not o); } void TAK(bool o = 1) { print(o ? "TAK" : "NIE"); } void NIE(bool o = 1) { TAK(not o); } #line 5 "YRS/all.hpp" #if (__cplusplus >= 202002L) #include constexpr ld pi = numbers::pi; #endif TE constexpr T inf = numeric_limits::max(); template <> constexpr i128 inf = i128(inf) * 2'000'000'000'000'000'000; template constexpr pair inf> = {inf, inf}; TE constexpr static inline int pc(T x) { return popcount(make_unsigned_t(x)); } constexpr static inline ll len(const Z &a) { return a.size(); } void reverse(Z &a) { reverse(all(a)); } void unique(Z &a) { sort(a); a.erase(unique(all(a)), a.end()); } TE vc inverse(const vc &a) { int N = len(a); vc b(N, -1); FOR(i, N) if (a[i] != -1) b[a[i]] = i; return b; } Z QMAX(const Z &a) { return *max_element(all(a)); } Z QMIN(const Z &a) { return *min_element(all(a)); } constexpr bool chmax(Z &a, const Z &b) { return (a < b ? a = b, 1 : 0); } constexpr bool chmin(Z &a, const Z &b) { return (a > b ? a = b, 1 : 0); } vc argsort(const Z &a) { vc I(len(a)); iota(all(I), 0); sort(I, [&](int i, int k) { return a[i] < a[k] or (a[i] == a[k] and i < k); }); return I; } TE vc rearrange(const vc &a, const vc &I) { int N = len(I); vc b(N); FOR(i, N) b[i] = a[I[i]]; return b; } template vc pre_sum(const vc &a) { int N = len(a); vc c(N + 1); FOR(i, N) c[i + 1] = c[i] + a[i]; if (of == 0) c.erase(c.begin()); return c; } TE constexpr static int topbit(T x) { if (x == 0) return - 1; if constexpr (sizeof(T) <= 4) return 31 - __builtin_clz(x); else return 63 - __builtin_clzll(x); } TE constexpr static int lowbit(T x) { if (x == 0) return -1; if constexpr (sizeof(T) <= 4) return __builtin_ctz(x); else return __builtin_ctzll(x); } TE constexpr T floor(T x, T y) { return x / y - (x % y and (x ^ y) < 0); } TE constexpr T ceil(T x, T y) { return floor(x + y - 1, y); } TE constexpr T bmod(T x, T y) { return x - floor(x, y) * y; } TE constexpr pair divmod(T x, T y) { T q = floor(x, y); return pair{q, x - q * y}; } template T SUM(const Z &v) { return accumulate(all(v), T(0)); } int lb(const Z &a, Z x) { return lower_bound(all(a), x) - a.begin(); } int lb(Z l, Z r, Z x) requires(is_same_v) { return lower_bound(l, r, x) - l; } int ub(const Z &a, Z x) { return upper_bound(all(a), x) - a.begin(); } int ub(Z l, Z r, Z x) requires(is_same_v) { return upper_bound(l, r, x) - l; } template ll bina(Z f, ll l, ll r) { if constexpr (ck) assert(f(l)); while (abs(l - r) > 1) { ll x = (r + l) >> 1; (f(x) ? l : r) = x; } return l; } TE T bina_real(Z f, T l, T r, int c = 100) { while (c--) { T x = (l + r) / 2; (f(x) ? l : r) = x; } return (l + r) / 2; } Z pop(Z &s) { if constexpr (requires { s.pop_back(); }) { Z x = s.back(); return s.pop_back(), x; } else if constexpr (requires { s.top(); }) { Z x = s.top(); return s.pop(), x; } else { Z x = s.front(); return s.pop(), x; } } void setp(int x) { cout << fixed << setprecision(x); } TE inline void sh(vc &a, int N) { a.resize(N, T(0)); } #line 1 "YRS/debug.hpp" #ifdef YRSD void DBG() { cerr << "]" << endl; } TES void DBG(T &&x, S &&...y) { cerr << x; if constexpr (sizeof...(S)) cerr << ", "; DBG(forward(y)...); } #define debug(...) cerr << "[" << __LINE__ << "]: [" #__VA_ARGS__ "] = [", DBG(__VA_ARGS__) void ERR() { cerr << endl; } TES void ERR(T &&x, S &&...y) { cerr << x; if constexpr (sizeof...(S)) cerr << ", "; ERR(forward(y)...); } #define err(...) cerr << "[" << __LINE__ << "]: ", ERR(__VA_ARGS__) #define asser assert #else #define debug(...) void(0721) #define err(...) void(0721) #define asser(...) void(0721) #endif #line 4 "No_96_\u570f\u5916\u3067\u3059.cpp" // #include "YRS/IO/fast_io.hpp" // #include "YRS/random/rng.hpp" #line 2 "YRS/ds/unionfind/dsu.hpp" struct dsu { int c; vc fa; dsu(int N = 0) : c(N), fa(N, -1) {} int f(int x) { while (fa[x] >= 0) { int p = fa[fa[x]]; if (p < 0) return fa[x]; x = fa[x] = p; } return x; } int operator[](int x) { return f(x); } bool merge(int x, int y) { x = f(x), y = f(y); if (x == y) return false; if (fa[x] > fa[y]) swap(x, y); fa[x] += fa[y]; fa[y] = x; --c; return true; } // set fa[y] = x; bool set(int x, int y) { x = f(x), y = f(y); if (x == y) return false; fa[x] += fa[y]; fa[y] = x; --c; return true; } int size(int x) { return -fa[f(x)]; } int count() const { return c; } bool same(int x, int y) { return f(x) == f(y); } void build(int N) { fa.assign(N, -1), c = N; } void reset() { std::fill(all(fa), -1), c = len(fa); } vc> get_group() { int N = len(fa); vc> v(N), s; FOR(i, N) v[f(i)].ep(i); FOR(i, N) if (not v[i].empty()) s.ep(v[i]); return s; } void pr() { const int N = len(fa); vc res(N); FOR(i, N) res[i] = f(i); print("fa:", res); } }; #line 2 "YRS/ge/pairs/furthest_pair.hpp" #line 2 "YRS/ge/basic/point.hpp" TE struct point { using P = point; T x, y; point(T x = 0, T y = 0) : x(x), y(y) {} P &operator+=(P p) { return x += p.x, y += p.y, *this; } P &operator-=(P p) { return x -= p.x, y -= p.y, *this; } P &operator*=(T w) { return x *= w, y *= w, *this; } P &operator/=(T w) { return x /= w, y /= w, *this; } P operator+(P p) const { return P(*this) += p; } P operator-(P p) const { return P(*this) -= p; } P operator*(T p) const { return P(*this) *= p; } P operator/(T p) const { return P(*this) /= p; } bool operator<(P p) const { return x != p.x ? x < p.x : y < p.y; } bool operator>(P p) const { return x != p.x ? x > p.x : y > p.y; } bool operator==(P p) const { return x == p.x and y == p.y; } bool operator!=(P p) const { return x != p.x or y != p.y; } P operator-() const { return P{-x, -y}; } T dot(P p) const { return x * p.x + y * p.y; } T det(P p) const { return x * p.y - y * p.x; } T square() const { return x * x + y * y; } ld length() const { return sqrtl(square()); } // [0, 2pi) 与 x轴 的夹角 ld angle() const { ld ang = atan2(y, x); return ang < 0 ? ang + pi * 2 : ang; } static ld angle(P A, P B, P C) { // ∠ABC 只求劣角 ld ang = atan2((A - B).det(C - B), (A - B).dot(C - B)); return abs(ang); } P rotate(double ang) const { // float 逆时针 ld C = cos(ang), S = sin(ang); return P{C * x - S * y, S * x + C * y}; } P rol90(bool ccw = true) const { return ccw ? P{-y, x} : P{y, -x}; } P nor() const { return (*this) / length(); } P div(P p) const { T d = p.square(); return P{(x * p.x + y * p.y) / d, (y * p.x - x * p.y) / d}; } }; TE istream &operator>>(istream &I, point &p) { return I >> p.x >> p.y; } TE ostream &operator<<(ostream &I, const point &p) { return I << p.x << ' ' << p.y; } // A -> B -> C 逆时针为 +1,顺时针为 -1。 TE int ccw(point a, point b, point c) { T x = (b - a).det(c - a); return x > 0 ? 1 : x < 0 ? -1 : 0; } #ifdef FIO TE void rd(point &p) { T x, y; IN(x, y); p = {x, y}; } TE void wt(point x) { wt(x.x); wt(' '); wt(x.y); } #endif #line 2 "YRS/ge/basic/hull.hpp" #line 4 "YRS/ge/basic/hull.hpp" template // 0 full 1 凹 2 凸 vc hull(const vc> &p, int mod = 0) { assert(mod >= 0 and mod <= 2); int N = len(p); if (N == 0) return {}; if (N == 1) return {0}; if (N == 2) { if (p[0] < p[1]) return {0, 1}; if (p[0] > p[1]) return {1, 0}; return {0}; } vc I = argsort(p); Z check = [&](int i, int j, int k) -> bool { T t = (p[j] - p[i]).det(p[k] - p[i]); if (NOT_SIE) return t >= 0; return t > 0; }; Z f = [&]() { vc s; for (int k : I) { while (len(s) > 1) { int i = s.end()[-2]; int j = s.end()[-1]; if (check(i, j, k)) break; s.pop_back(); } s.ep(k); } return s; }; vc s; if (mod == 0 or mod == 1) { Z a = f(); s.insert(s.end(), all(a)); } if (mod == 0 or mod == 2) { if (not s.empty()) s.pop_back(); reverse(I); Z a = f(); s.insert(s.end(), all(a)); } if (mod == 2) reverse(s); while (len(s) > 1 and p[s[0]] == p[s.back()]) s.pop_back(); while (len(s) > N) s.pop_back(); return s; } #line 5 "YRS/ge/pairs/furthest_pair.hpp" // https://judge.yosupo.jp/problem/furthest_pair // https://www.luogu.com.cn/problem/P1452 // https://www.luogu.com.cn/problem/P4357 // https://www.luogu.com.cn/problem/P6247 // 如果浮点数精度不够可以考虑乘一个大整数,后面再除掉 TE PII furthest_pair(const vc> &p) { T mx = -1; PII ans = {-1, -1}; Z f = [&](int i, int k) -> void { if (chmax(mx, (p[i] - p[k]).square())) ans = {i, k}; }; f(0, 1); vc I = hull(p); int N = len(I); if (N == 1) return ans; if (N == 2) return {I[0], I[1]}; I.insert(I.end(), all(I)); Z C = rearrange(p, I); int k = 1; FOR(i, N) { chmax(k, i); while (k < 2 * N and (C[i + 1] - C[i]).det(C[k + 1] - C[k]) > 0) ++k; f(I[i], I[k]); } return ans; } #line 2 "YRS/ds/basic/hashmap.hpp" TE struct hash_map { uint ls, msk; vc ke; vc val; vc vis; ull hash(ull x) const { static const ull FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count(); x += FIXED_RANDOM; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return (x ^ (x >> 31)) & msk; } void extend() { vc> dat; const int N = len(vis); dat.reserve(N / 2 - ls); FOR(i, N) if (vis[i]) dat.ep(ke[i], val[i]); build(dat.size() << 1); for (Z &[a, b] : dat) (*this)[a] = b; } hash_map(uint N = 0) { build(N); } void build(uint N) { uint k = 8; while (k < (N << 1)) k <<= 1; ls = k >> 1, msk = k - 1; ke.resize(k), val.resize(k), vis.assign(k, 0); } void clear() { fill(all(vis), 0); ls = (msk + 1) >> 1; } ll size() const { return vis.size() / 2 - ls; } int id(ull k) const { int i = hash(k); while (vis[i] and ke[i] != k) i = (i + 1) & msk; return i; } T &operator[](ull k) { if (ls == 0) extend(); int i = id(k); if (not vis[i]) { vis[i] = 1; ke[i] = k; val[i] = T {}; --ls; } return val[i]; } T get(ull k, T fail) const { int i = id(k); return (vis[i] ? val[i] : fail); } bool contains(ull k) const { int i = id(k); return vis[i] and ke[i] == k; } vc> get_all() const { int N = len(vis); vc> s; FOR(i, N) if (vis[i]) s.ep(ke[i], val[i]); return s; } // f(ke, val); void enumerate_all(Z f) const { const int N = len(vis); FOR(i, N) if (vis[i]) f(ke[i], val[i]); } }; #line 9 "No_96_\u570f\u5916\u3067\u3059.cpp" #define tests 0 #define fl 0 #define DB 10 using P = point; void Yorisou() { INT(N); if (N == 0) return print(1); VEC(P, a, N); FOR(i, N) a[i].x += 10000, a[i].y += 10000; hash_map mp; FOR(i, N) mp[a[i].x << 30 | a[i].y] = i; dsu g(N); FOR(i, N) { ll x = a[i].x, y = a[i].y; FOR(k, 11) { FOR(j, 11) { if (k * k + j * j > 100) break; for (ll d : {-1, 1}) { ll xx = x + k, yy = y + j * d; if (mp.contains(xx << 30 | yy)) g.merge(i, mp[xx << 30 | yy]); } } } } vc> s = g.get_group(); ll mx = 0; for (vc &s : s) if (len(s) > 1) { vc

p; for (int i : s) p.ep(a[i]); Z [a, b] = furthest_pair(p); chmax(mx, (p[a] - p[b]).square()); } setp(9); print(sqrtl(mx) + 2); } #line 1 "YRS/aa/main.hpp" int main() { cin.tie(nullptr)->sync_with_stdio(0); int T = 1; if (fl) cerr.tie(0); if (tests and not fl) IN(T); for (int i = 0; i < T or fl; ++i) { Yorisou(); if (fl and i % DB == 0) cerr << "Case: " << i << '\n'; } return 0; } #line 46 "No_96_\u570f\u5916\u3067\u3059.cpp"