// 想定解法: バケット + Union-Find + 凸包 // 計算量: O(NlogN) // 参考 // http://www-ikn.ist.hokudai.ac.jp/~k-sekine/slides/convexhull.pdf // http://www.prefield.com/algorithm/geometry/convex_hull.html // http://www.prefield.com/algorithm/geometry/ccw.html // http://www.prefield.com/algorithm/geometry/convex_diameter.html #include using namespace std; void rc(int v,int mn,int mx){if(v P; const int MAXN = 120000, MINXY = -10000, MAXXY = +10000; const int RANGE = 10*10; int N, X[MAXN+1], Y[MAXN+1]; int norm(int i,int j){int x=X[i]-X[j],y=Y[i]-Y[j];return x*x+y*y;} class uf_ { public: vector node; uf_(int n) : node(n, -1){;} void con(int n, int m){ n = root(n); m = root(m); if(n == m) return; node[n] += node[m]; node[m] = n; } bool is_con(int n, int m){ return root(n) == root(m); } int root(int n){ return (node[n] < 0) ? n : node[n] = root(node[n]); } int size(int n){ return -node[root(n)]; } }; int inprd(const P &a, const P &b){ return (conj(a) * b).real(); } int outprd(const P &a, const P &b){ return (conj(a) * b).imag(); } // http://www.prefield.com/algorithm/geometry/ccw.html int ccw(int i, int j, int k) { P a(X[i],Y[i]),b(X[j],Y[j]),c(X[k],Y[k]); b -= a; c -= a; if(outprd(b, c) > 0) return +1; // counter clockwise if(outprd(b, c) < 0) return -1; // clockwise if(inprd(b, c) < 0) return +2; // c--a--b on line if(norm(b) < norm(c)) return -2; // a--b--c on line return 0; } // http://www.prefield.com/algorithm/geometry/convex_hull.html vector convex_hull(vector ps) { int n = ps.size(), k = 0; if(n < 3) return ps; sort(ps.begin(), ps.end(), [](int i, int j){ return ((X[i]!=X[j])?(X[i] ch(2*n); // lower-hull for(int i = 0; i < n; ch[k++] = ps[i++]){ while(k >= 2 && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k; } // upper-hull for(int i = n-2, t = k+1; i >= 0; ch[k++] = ps[i--]){ while(k >= t && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k; } ch.resize(k-1); return ch; } vector v[(MAXXY-MINXY)/10+1][(MAXXY-MINXY)/10+1]; int main(){ //freopen("in/05.txt", "r", stdin); // input : O(N) cin >> N; rc(N, 0, MAXN); REP(i, N){ cin >> X[i] >> Y[i]; rc(X[i], MINXY, MAXXY); rc(Y[i], MINXY, MAXXY); v[(Y[i]-MINXY)/10][(X[i]-MINXY)/10].push_back(i); } if(N == 0){ cout << 1 << endl; return 0; } uf_ uf(N); // O(N*900) REP(i,N){ int dx = (X[i]-MINXY)/10; int dy = (Y[i]-MINXY)/10; for(int y = -1; y <= 1; y++){ if(dy+y < 0 || dy+y > (MAXXY-MINXY)/10) continue; for(int x = -1; x <= 1; x++){ if(dx+x < 0 || dx+x > (MAXXY-MINXY)/10) continue; for(auto &j : v[dy+y][dx+x]){ if(i == j) continue; if(norm(i,j) <= RANGE) uf.con(i,j); } } } } // 点集合を各クラスタに分割: O(NlogN) map > m; REP(i,N) m[uf.root(i)].push_back(i); // クラスタ毎に凸包を取って最遠点対を求める map stat; int maxr = 0; for(auto &it : m){ auto ch = convex_hull(it.second); int n = ch.size(); stat[n]++; // このへんまでで最大でも N=1300 程度まで落ちるので O(N^2) REP(i,n) REP(j,n){ if(i == j) continue; maxr = max(maxr, norm(ch[i],ch[j])); } } for(auto &v : stat) cerr << v.first << ":" << v.second << "/"; cerr<