#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]; } } 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; for(int att=0;att<1;att++){ vector cp=p; vector cres; vector trash(n,0); trash[0]=1; for(int hd=0;hd<50;hd++){ vector lis; for(int i=1;i up=cp; shrink(i,up); vector up2; for(int j=1;j ch=convex_hull(up2); if(jud(ch)){lis.push_back(i);} } if(lis.empty()){break;} int tg=xor128()%lis.size(); cres.push_back(lis[tg]); shrink(lis[tg],cp); vector cp2; for(int j=1;j ch=convex_hull(cp2); for(auto &nx : ch){ long long ox=nx.first; long long oy=nx.second; } trash[lis[tg]]=1; } reverse(cres.begin(),cres.end()); res=cres; } 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; }