#include #include #include #include #include #include using namespace std; typedef long long int ll; typedef complex Point; typedef vector Polygon; // 多角形 const long double eps=1e-9; namespace std{ bool operator<(const Point &p,const Point &q){ if(p.real()q.real()+eps) return false; return p.imag()eps){ return 1; // a,b,cが反時計回りの順に並ぶ } if(cross(b,c)<-eps){ return -1; // a,b,cが時計回りの順に並ぶ } if(dot(b,c)<0){ return 2; // c,a,bがこの順に一直線に並ぶ } if(norm(b) ps){ int n=(int)ps.size(); int k=0; // 凸包の頂点数 sort(ps.begin(),ps.end()); Polygon qs(2*n); // 構築中の凸包 for(int i=0;i=2&&ccw(qs[k-2],qs[k-1],ps[i])<=0) --k; } for(int i=n-2,t=k+1;i>=0;qs[k++]=ps[i--]){ while(k>=t&&ccw(qs[k-2],qs[k-1],ps[i])<=0) --k; } qs.resize(k-1); return qs; } // 凸多角形の直径 pair,long double> convex_diameter(const Polygon& poly){ int n=(int)poly.size(); if(n==2){ return make_pair(make_pair(0,1),abs(poly[0]-poly[1])); } int i=0,j=0; // ある方向に最も遠い点対 // x軸方向に最も遠い点対を求める for(int k=0;kpoly[i].imag())i=k; if(poly[k].imag() resp=make_pair(-1,-1); long double resd=0; int si,maxi,sj,maxj; si=maxi=i; sj=maxj=j; while(si!=maxj || sj!=maxi){ long double cur=abs(poly[si]-poly[sj]); if(resd+eps par,num; vector done; UnionFind(int n):par(n),num(n,1),done(n,false){ iota(par.begin(),par.end(),0); //include } int find(int v){ return (par[v]==v)?v:(par[v]=find(par[v])); } void unite(int u,int v){ u=find(u),v=find(v); if(u==v)return; if(num[u]> n; if(n==0){ cout << 1 << endl; return 0; } Polygon ps; vector > > backet(2010,vector >(2010)); for(int i=0;i> x[i] >> y[i]; ps.push_back(Point(x[i],y[i])); x[i]+=10000; y[i]+=10000; backet[x[i]/10][y[i]/10].push_back(i); } UnionFind uf(n); for(int i=0;i<2010;i++){ for(int j=0;j<2010;j++){ for(auto v:backet[i][j]){//近接するブロックを探索する for(int k=0;k<9;k++){ int ni=i+dx[k],nj=j+dy[k]; if(ni<0||nj<0)continue; for(auto vv:backet[ni][nj]){ if(v==vv)continue; if(abs(ps[v]-ps[vv])<10+eps){ uf.unite(v,vv); } } } } } } vector Polys(n); for(int i=0;i