#include using namespace std; using pii=pair; using tii=tuple; using qii=tuple; using ll=long long; using ull=unsigned long long; using ld=long double; constexpr int INF=1e9; constexpr ll INF_ll=1e18; #define rep(i,n) for (int i=0;i<(int)(n);i++) #define replr(i,l,r) for (int i=(int)(l);i<(int)(r);i++) #define all(v) v.begin(),v.end() #define len(v) ((int)v.size()) template inline bool chmin(T &a,T b){ if(a>b){ a=b; return true; } return false; } template inline bool chmax(T &a,T b){ if(a inline bool chmin_ref(T &a,const T &b){ if(a>b){ a=b; return true; } return false; } template inline bool chmax_ref(T &a,const T &b){ if(a(now-start).count(); return ms; } int get_ms_all_program(){ auto now=chrono::steady_clock::now(); int ms=chrono::duration_cast(now-program_start).count(); return ms; } } mt19937 mt; uint32_t rand_int(uint32_t r){ //[0,r) assert(r!=0); return ((uint64_t)mt()*r)>>32; } int rand_int(int l,int r){ //[l,r) assert(l T get_random_element(const vector &v){ assert(!v.empty()); return v[rand_int(len(v))]; } template void add(vector &a,vector b){ for(auto i:b) a.push_back(i); } template SA_State SA(const SA_State &first_state,int limit_ms,double start_temp,double end_temp=0.0){ SA_State state=first_state,best_state=state; int loop_cnt=0,accept_cnt=0,update_cnt=0; int ms=0; double temp=start_temp; Timer::snap(); while(true){ if((loop_cnt&63)==63){ ms=Timer::get_ms(); if(limit_ms<=ms) break; //double t=(double)ms/limit_ms; temp=start_temp-(start_temp-end_temp)/limit_ms*ms; //temp=pow(start_temp,1-t)*pow(end_temp,t); } loop_cnt++; double accept_diff=log(rand_double())*temp; bool accepted=state.modify(accept_diff); if(accepted){ accept_cnt++; if(state.score A,B; constexpr ll L=5e17,M=1e18; ll calc_score(const vector &ord){ array a=A,b=B; for(auto e:ord){ a[0]=a[e]=(a[0]+a[e])/2; b[0]=b[e]=(b[0]+b[e])/2; } return max(abs(L-a[0]),abs(L-b[0])); } namespace Solver{ struct State{ vector ord; double score=0; State():ord(N-1){ rep(i,N-1){ ord[i]=1+i; } score=calc_score(); } double calc_score() const{ return log10(::calc_score(ord)+1); } bool modify(double accept_diff){ int a=rand_int(N-1),b=rand_int(N-1); swap(ord[a],ord[b]); double new_score=calc_score(); if(accept_diff<=score-new_score){ score=new_score; return true; }else{ swap(ord[a],ord[b]); return false; } } }; void dfs(int k,ll x,ll y,vector &cand,vector &used,vector &ord,ll &best_score,vector &best_ord){ static int loop=0; static bool fin=false; if(fin) return; loop++; if((loop&1023)==0){ if(900>(N-1-k)); ll ny=y+(B[cand[i]]>>(N-1-k)); if(10000>(N-1-k))-L<-10000) continue; if(10000>(N-1-k))-L<-10000) continue; used[i]=true; ord[k]=cand[i]; dfs(k-1,nx,ny,cand,used,ord,best_score,best_ord); ord[k]=-1; used[i]=false; } } void solve(){ State state; state=SA(state,100,0.2,0.2); vector ord=state.ord; ll best_score=calc_score(ord); vector best_ord=ord; replr(s,1,N-1){ ll x=0,y=0; replr(i,s,N-1){ x+=A[ord[i]]>>(N-1-i); y+=B[ord[i]]>>(N-1-i); } vector cand; vector now_ord=ord; rep(i,s){ cand.push_back(ord[i]); now_ord[i]=-1; } vector used(len(cand),false); dfs(s-1,x,y,cand,used,now_ord,best_score,best_ord); } cout << len(best_ord) << '\n'; for(auto e:best_ord){ cout << 1 << ' ' << e+1 << '\n'; } cerr << (int)floor(2000000-100000*log10(best_score+1)) << ' ' << Timer::get_ms() << '\n'; } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); Timer::program_start_snap(); int n; cin >> n; assert(n==N); rep(i,N) cin >> A[i] >> B[i]; Solver::solve(); exit(0); }