#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 long double D; const D INF = 1e12,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 D 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; D maxd = abs(ps[is] - ps[js]); int i = is, maxi = is, j =js, maxj=js; do { if(cross(ps[pmod(i+1,n)]-ps[i],ps[pmod(j+1,n)]-ps[j]) >= 0) j = pmod(j+1,n); else i = pmod(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). } // 凸多角形を反時計周りでソート // O(nlogn) // verified by AOJLIB // http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1092743 void ccw_sort(ConvexPoly &ps){ const int n=ps.size(); sort(ALL(ps)); const P& O = ps[0]; sort(ps.begin()+1,ps.end(),[&O](const P& l,const P& r) -> bool{return cross(l-O,r-O) > 0;}); int sr=1;while(sr < n && cross(ps[sr]-O,ps[1]-O)==0)sr++; sort(ps.begin()+1,ps.begin()+sr,[&O](const P& l,const P& r) -> bool{return abs(l-O)=1 && cross(ps[el-1]-O,ps[n-1]-O)==0)el--; sort(ps.begin()+el,ps.end(),[&O](const P& l,const P& r) -> bool{return abs(l-O)>abs(r-O);}); } } using namespace _convex_poly; int main(){ cin.tie(0); ios::sync_with_stdio(false); cout <> N; vector > psint(N); REP(i,N){ int x,y;cin >> x >> y; psint[i]=make_pair(x,y); } sort(ALL(psint)); vector > ps(N); map,int> pmap; REP(i,N){ pmap[psint[i]]=i; ps[i]=complex(psint[i].first,psint[i].second); } UnionFind uf(N); REP(i,N)for(int dx=-10;dx<=10;dx++)for(int dy=-10;dy<=10;dy++) if(pmap.count(make_pair(psint[i].first+dx,psint[i].second+dy)) && dx*dx+dy*dy<=100){ uf.unite(i, pmap[make_pair(psint[i].first+dx,psint[i].second+dy)]); } sort(ALL(ps)); D Mv=1; if(N>0)Mv=2; map> vs;REP(i,N)vs[uf.par[i]].push_back(ps[i]); EACH(it,vs)if(it->second.size()>=2){ sort(ALL(it->second)); it->second=convex_hull(it->second); Mv=max(Mv,convex_diameter(it->second)+2); } cout << Mv <