#include // c #include #include // io #include #include #include #include // container #include #include #include #include #include #include // other #include #include #include #include #include #include using namespace std; typedef long long ll; #define ALL(c) (c).begin(),(c).end() #define FOR(i,l,r) for(int i=(int)l;i<(int)r;++i) #define REP(i,n) FOR(i,0,n) #define FORr(i,l,r) for(int i=(int)r-1;i>=(int)l;--i) #define REPr(i,n) FORr(i,0,n) #define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i) #define IN(l,v,r) ((l)<=(v) && (v)<(r)) #define UNIQUE(v) v.erase(unique(ALL(v)),v.end()) //debug #define DUMP(x) cerr << #x << " = " << (x) #define LINE() cerr<< " (L" << __LINE__ << ")" template T pmod(T x,U M){return (x%M+M)%M;} struct UnionFind{ vector par,rank,ss;int size; UnionFind(int n){ REP(i,n) par.push_back(i); rank = vector(n);ss=vector(n,1);size=n; } int root(int x){ if(par[x] == x)return x; return par[x] = root(par[x]); } bool same(int x,int y){ return root(x) == root(y); } void unite(int x,int y){ x = root(x);y = root(y); if(x==y)return; if(rank[x] < rank[y]){ par[x] = y;ss[y]+=ss[x]; }else{ par[y] = x;ss[x]+=ss[y]; } if(rank[x] == rank[y]) rank[x]++; size--; } int getS(int x){ return ss[root(x)]; } }; // must template typedef double D; const D INF = 1e20,EPS = 1e-8; typedef complex P; #define X real() #define Y imag() istream& operator >> (istream& is,P& p){D x,y;is >> x >> y; p=P(x,y); return is;} int sig(D a,D b=0){return ab+EPS?1:0;} template bool eq(const T& a,const T& b){return sig(abs(a-b))==0;} bool compX (const P& a,const P& b){return !eq(a.X,b.X)?sig(a.X,b.X)<0:sig(a.Y,b.Y)<0;} namespace std{ bool operator < (const P& a,const P& b){return compX(a,b);} bool operator == (const P& a,const P& b){return eq(a,b);} }; // a×b D cross(const P& a,const P& b){return imag(conj(a)*b);} // a・b D dot(const P& a,const P& b) {return real(conj(a)*b);} int ccw(const P& a,P b,P c){ b -= a; c -= a; if (sig(cross(b,c)) > 0) return +1; // counter clockwise if (sig(cross(b,c)) < 0) return -1; // clockwise if (sig(dot(b,c)) < 0) return +2; // c--a--b on line if (sig(norm(b),norm(c))<0) return -2; // a--b--c on line return 0; //a--c--b on line (c==b,c==a) } // //must template namespace _convex_poly{ typedef vector

Poly,ConvexPoly; // 凸包 //O(n logn) // verified by AOJLIB // http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1092743 ConvexPoly convex_hull(Poly ps) { int n = ps.size(), k = 0; sort(ALL(ps)); Poly ch(2*n); REP(i,n){ // lower-hull while (k > 1 && cross(ch[k-1]-ch[k-2],ps[i]-ch[k-1]) < 0) --k; ch[k++]=ps[i]; } for(int i=n-2,t=k;i>=0;i--){// upper-hull while (k > t && cross(ch[k-1]-ch[k-2],ps[i]-ch[k-1]) < 0) --k; ch[k++]=ps[i]; } ch.resize(k-1); return ch; } // 凸多角形の直径 // O(n) // verified by AOJLIB // http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1092749 double convex_diameter(const ConvexPoly &ps) { const int n = ps.size(); int is=0;REP(i,n)if(ps[i].Y > ps[is].Y) is = i; int js=0;REP(j,n)if(ps[j].Y < ps[js].Y) js = j; double maxd = abs(ps[is] - ps[js]); int i = is, maxi = is, j =js, maxj=js; do { if(cross(ps[(i+1)%n]-ps[i],ps[(j+1)%n]-ps[j]) >= 0) j = (j+1)%n; else i = (i+1)%n; if(abs(ps[i]-ps[j]) > maxd) maxd = abs(ps[i]-ps[j]);maxi = i; maxj = j; } while (i != is || j != js); return maxd; // farthest pair is (maxi, maxj). } } using namespace _convex_poly; int main(){ cin.tie(0); ios::sync_with_stdio(false); cout <,int> pmap; REP(i,N){ int x,y;scanf("%d%d",&x,&y); pmap[make_pair(x,y)]=i; } vector> ds; for(int dx=-10;dx<=10;dx++)for(int dy=-10;dy<=10;dy++)if(dx*dx+dy*dy<=100){ ds.push_back(make_pair(dx,dy)); } UnionFind uf(N); EACH(it,pmap)REP(j,ds.size()){ pair p(it->first.first+ds[j].first,it->first.second + ds[j].second); if(pmap.count(p))uf.unite(it->second,pmap[p]); } double Mv=1; if(N>0)Mv=2; vector> vs(N);EACH(it,pmap)vs[uf.par[it->second]].push_back(P(it->first.first,it->first.second)); REP(i,vs.size())if(vs[i].size()>=2){ vs[i]=convex_hull(vs[i]); Mv=max(Mv,convex_diameter(vs[i])+2); } cout << Mv <