#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 i128=__int128; using pll=pair; i128 det(long long a,long long b,long long c,long long d){ i128 l=a; l*=d; i128 r=b; r*=c; return (l-r); } 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 && det((L[j-1].first-L[j-2].first),(L[j-1].second-L[j-2].second),(P[i].first-L[j-2].first),(P[i].second-L[j-2].second))<=0){ 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 && det((H[j-1].first-H[j-2].first),(H[j-1].second-H[j-2].second),(P[i].first-H[j-2].first),(P[i].second-H[j-2].second))<=0){ 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=0;i; vector gensuf(int remhd,vector p){ int n=p.size(); vector id(n-1); for(int i=0;i res; vector> ppi; for(int i=0;i up=p; shrink(i,up); vector htg; for(int j=0;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=(gx-target)*(gx-target)+(gy-target)*(gy-target); if(gp > gd){ gp=gd; tg=i; } } } if(tg==-1){break;} shrink(tg,p); res.push_back({0,id[tg]}); for(int i=tg;i &op,vector &p){ for(auto &nx : op){ p[nx.first]=f(p[nx.first],p[nx.second]); p[nx.second]=p[nx.first]; } } long long eval(vector &op,vector p){ simu(op,p); return max(abs(p[0].first-target),abs(p[0].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; res=gensuf(50,p); vector ex(n,0); for(int i=0;i900000){break;} for(int i=0;i<20;i++){ for(int j=0;j=csc){ sc=csc; } else{ res[i].first=pj; res[i].second=pk; } } } } for(int i=0;i<15;i++){ for(int j=i+1;j<15;j++){ for(int k=1;k=csc){ sc=csc; } else{ res[i].second=pk; res[j].second=pl; } } } } } } cout << res.size() << "\n"; for(auto &nx : res){ cout << nx.first+1 << " " << nx.second+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; }