#pragma GCC target("avx2") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include #include using namespace std; long long start_time; void start_clock(){ struct timeval tv; gettimeofday(&tv, NULL); start_time=(tv.tv_sec*1000000+tv.tv_usec); } long long current_clock(){ struct timeval tv; gettimeofday(&tv, NULL); long long current_time=(tv.tv_sec*1000000+tv.tv_usec); // cout << current_time-start_time << "(us)\n"; return current_time-start_time; } unsigned long long xor128(){ static unsigned long long x=123456789,y=362436069,z=521288629,w=88675123; unsigned long long t; t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); } using p128=pair<__int128,__int128>; using i128=__int128; vector convex_hull(vector P){ // Copyright (c) 2023 0214sh7 // https://github.com/0214sh7/library/ if(P.size()<=2){ return P; } vector H,L,R; sort(P.begin(),P.end()); //下半分 for(int i=0;i=2 && (L[j-1].first-L[j-2].first)*(P[i].second-L[j-2].second)<=(L[j-1].second-L[j-2].second)*(P[i].first-L[j-2].first)){ L.pop_back(); j--; } L.push_back(P[i]); } //上半分 for(int i=P.size()-1;i>=0;i--){ int j=H.size(); while(j>=2 && (H[j-1].first-H[j-2].first)*(P[i].second-H[j-2].second)<=(H[j-1].second-H[j-2].second)*(P[i].first-H[j-2].first)){ H.pop_back(); j--; } H.push_back(P[i]); } R=L; for(int i=1;i &P){ int n=P.size(); for(int i=0;i &p){ for(int i=1;i &op,vector &p){ for(auto &nx : op){ p[0]=f(p[0],p[nx]); p[nx]=p[0]; } } long long eval(p128 x){ return max(x.first-target,x.second-target); } int main(){ start_clock(); ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector p(n); for(int i=0;i> x >> y; p[i].first=x; p[i].second=y; } vector res; vector trash(n,0); trash[0]=1; vector cp=p; for(int hd=0;hd<50;hd++){ int tg=-1; i128 gp=1e37; for(int i=1;i up=cp; shrink(i,up); vector htg; for(int j=1;j ch=convex_hull(htg); if(jud(ch)){ i128 gx=0,gy=0; for(auto &nx : ch){ gx+=nx.first; gy+=nx.second; } gx/=ch.size(); gy/=ch.size(); i128 gd=max((gx-target)*(gx-target),(gy-target)*(gy-target)); if(gp > gd){ gp=gd; tg=i; } } } if(tg==-1){break;} shrink(tg,cp); // cout << hd << " : "; // for(auto &nx : cp){ // long long ox=nx.first; // long long oy=nx.second; // cout << ox << " " << oy << "\n"; // } res.push_back(tg); trash[tg]=1; } reverse(res.begin(),res.end()); cout << res.size() << "\n"; for(auto &nx : res){ cout << 1 << " " << nx+1 << "\n"; } // simu(res,p); // for(auto &nx : p){ // long long ox=nx.first; // long long oy=nx.second; // cout << ox << " " << oy << "\n"; // } return 0; }