#include typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() using namespace std; template struct Pt { T x, y; Pt(T x0, T y0) : x(x0), y(y0) {} Pt() :x(0),y(0) {} Pt(const Pt &other) :x(other.x),y(other.y) {} Pt &operator=(const Pt& other) { x = other.x; y = other.y; return *this; } const Pt operator+(const Pt &other) const { return Pt(other.x+x, other.y+y); } const Pt operator-(const Pt &other) const { return Pt(other.x-x, other.y-y); } Pt &operator+=(const Pt &other) { x += other.x; y += other.y; return *this; } Pt &operator-=(const Pt &other) { x -= other.x; y -= other.y; return *this; } Pt operator*(double r) const { return Pt(x*r, y*r); } bool operator==(const Pt &other) const { return (x==other.x && y==other.y); } bool operator!=(const Pt &other) const { return !(operator==(other)); } bool operator<(const Pt &other) const { return (x < other.x)? true : ((x==other.x)? (y < other.y) : false); } bool operator<=(const Pt &other) const { return (*this == other)? true : (*this < other); } bool operator>(const Pt &other) const { return (other < *this); } bool operator>=(const Pt &other) const { return (other <= *this); } double norm(void) const { return hypot(x, y); } // class method static double cross(const Pt &a, const Pt &b) { return ((double)a.y*b.x - (double)a.x*b.y); } static double dot(const Pt &a, const Pt &b) { return (double)a.x*b.x+(double)a.y*b.y; } // O(n*log(n)) static std::vector convex_hull(std::vector &ps) { std::sort(ps.begin(), ps.end()); int k = 0; int n = ps.size(); vector qs(2*n); for (int i = 0; i < n; ++i) { while (k > 1 && cross(qs[k-1]-qs[k-2], ps[i]-qs[k-1]) <= 0) --k; qs[k++] = ps[i]; } for (int i = n-2, t = k; i >= 0; --i) { while (k > t && cross(qs[k-1]-qs[k-2], ps[i]-qs[k-1]) <= 0) --k; qs[k++] = ps[i]; } qs.resize(k-1); qs.shrink_to_fit(); return std::move(qs); } // convex_diameter // O(n*log(n)) static double convex_diameter(std::vector &ps) { auto qs = convex_hull(ps); int n = qs.size(); auto dist = [](const Pt &a, const Pt &b) { return sqrt(dot(a-b, a-b)); }; if (n == 2) return dist(qs[0], qs[1]); int i,j; i = j = 0; for (int k = 0; k < n; ++k) { if ( !(qs[i] < qs[k]) ) i = k; if (qs[j] < qs[k]) j = k; } double res = 0; int si = i, sj = j; while ( !(i == sj && j == si) ) { res = max(res, dist(qs[i], qs[j])); int di = (i+1)%n; int dj = (j+1)%n; if (cross(qs[di]-qs[i], qs[dj]-qs[j]) < 0) i = di; else j = dj; } return res; } friend std::ostream &operator<<(std::ostream &os, const Pt &p) { os <<"("< Pt operator*(double r, const Pt &p) { return p*r; } class UFTree { std::vector par_; std::vector rank_; int size_; public: UFTree(int N) { init(N); } UFTree() {} ~UFTree() {} void init(int N) { par_.resize(N); rank_.resize(N, 0); for (int i = 0; i < N; ++i) par_[i] = i; size_ = N; } int find(int x) { assert(0 <= x && x < par_.size()); if ( par_[x] == x ) return x; else return ( par_[x] = find(par_[x])); } void unite(int x, int y) { assert(0 <= x && x < par_.size()); assert(0 <= y && y < par_.size()); x = find(x); y = find(y); if ( x == y ) return; --size_; if ( rank_[x] < rank_[y] ) par_[x] = y; else { par_[y] = x; if ( rank_[x] == rank_[y] ) ++rank_[x]; } } bool same(int x, int y) { return (find(x) == find(y)); } size_t size() { return size_; } // find 経由で par を更新してからでないと par へのアクセスは危険 int operator[](size_t i) { return find(i); } }; class NoService { public: void solve(void) { int N; cin>>N; // 中継局がないときは 1km if (N==0) { cout<<1<>> bucket(M+1,vector>(M+1, vector())); vector> ps; REP(i,N) { int x,y; cin>>x>>y; ps.emplace_back(x,y); bucket[(x+offset)/B][(y+offset)/B].push_back(i); } // bucket を使って UFTree を更新 REP(i,N) { int xi = (ps[i].x+offset)/B; int yi = (ps[i].y+offset)/B; // 隣接する 9 バケットを探索 REP(ii,3) REP(jj,3) { int xi2 = xi+dx[ii]; int yi2 = yi+dy[jj]; if (xi2 < 0 || xi2 > M || yi2 < 0 || yi2 > M) continue; for (auto k : bucket[xi2][yi2]) { if (k == i) continue; if ( (ps[k]-ps[i]).norm() <= 10 ) uft.unite(k,i); } } } vector>> group(N); REP(i,N) group[uft[i]].push_back(ps[i]); double ans = 0; REP(i,N) { if (uft[i]==i) ans = max(ans, Pt::convex_diameter(group[uft[i]])); } cout<solve(); delete obj; return 0; } #endif