#include using namespace std; template struct Point{ public: T x,y; Point() : x(0),y(0) {} Point(T a,T b) : x(a),y(b) {} Point &operator=(const Point &b) = default; Point operator+(const Point &b){return Point(x+b.x,y+b.y);} Point operator-(const Point &b){return Point(x-b.x,y-b.y);} Point operator+=(const Point &b){return *this=*this+b;} Point operator-=(const Point &b){return *this=*this-b;} bool operator==(const Point &b){return x==b.x && y==b.y;} bool operator!=(const Point &b){return x!=b.x || y!=b.y;} bool operator<(const Point &b){ if(x == b.x) return y < b.y; else return x < b.x; } bool operator<=(const Point &b){return (*this) < b || (*this) == b;} bool operator>(const Point &b){return !((*this) <= b);} bool operator>=(const Point &b){return !((*this) < b);} friend T inner(const Point a,const Point b){return a.x*b.x+a.y*b.y;} friend T cross(const Point a,const Point b){return a.x*b.y-a.y*b.x;} friend T twodist(const Point a,const Point b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}//2乗で返す. }; template istream &operator>>(istream &is,Point &a){ is >> a.x >> a.y; return is; } template ostream &operator<<(ostream &os,Point &a){ os << a.x << " " << a.y; return os; } template vector> Convexhull(vector> &P){ //(x,y)が最小の点から時計回りに頂点を返す. //(xi,yi)と(xi+1,yi+1)は辺になる |P|=1の時注意. sort(P.begin(),P.end()); P.erase(unique(P.begin(),P.end()),P.end()); if(P.size() == 0) return {}; if(P.size() == 1) return {P.at(0),P.at(0)}; vector> A,B; for(auto &p1 : P){ while(A.size() >= 2){ auto &p2 = A.at(A.size()-1); auto &p3 = A.at(A.size()-2); T check = cross(p2-p1,p3-p2); if(check <= 0) A.pop_back(); else break; } A.push_back(p1); } for(auto &p1 : P){ while(B.size() >= 2){ auto &p2 = B.at(B.size()-1); auto &p3 = B.at(B.size()-2); T check = cross(p2-p1,p3-p2); if(check >= 0) B.pop_back(); else break; } B.push_back(p1); } for(int i=B.size()-2; i>=0; i--) A.push_back(B.at(i)); return A; } class UnionFind{ private: vector par,siz; public: UnionFind(int N){ par.resize(N,-1); siz.resize(N,1); } int root(int x){ //連結成分の代表頂点を返す. if(par.at(x) == -1) return x; else return par.at(x) = root(par.at(x)); } bool unite(int u, int v){ //u,vを連結する 連結してた->false,した->trueを返す. u = root(u),v = root(v); if(u == v) return false; if(siz.at(u) < siz.at(v)) swap(u,v); //Union by size. par.at(v) = u; siz.at(u) += siz.at(v); return true; } bool issame(int u, int v){ //同じ連結成分ならtrue. if(root(u) == root(v)) return true; else return false; } int size(int pos){return siz.at(root(pos));} //posの連結成分の大きさを返す. }; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; if(N == 0){cout << 1 << endl; return 0;} vector> P(N); for(auto &p : P) cin >> p,p.x += 10000,p.y += 10000; map,int> M; const int n = 20000; vector>> Xs(n+1); for(int i=0; i OK(11); for(int i=0; i<=10; i++){ for(int k=0; ; k++){ int diff = i*i+k*k; if(diff <= 100) OK.at(i) = k; else break; } } UnionFind Z(N); for(int i=0; i 20000) break; int ly = y-OK.at(dx),ry = y+OK.at(dx); auto &X = Xs.at(x); int pos = lower_bound(X.begin(),X.end(),pair{ly,-1})-X.begin(); while(pos < X.size() && X.at(pos).first <= ry) Z.unite(i,X.at(pos).second),pos++; } } vector> G(N); for(int i=0; i> now; for(auto &p : g) now.push_back(P.at(p)); auto con = Convexhull(now); con.pop_back(); int pos = 0,n = con.size(); for(int i=0; i