using System; using System.Diagnostics; using System.Reflection; // TODO: 1次元で考える // 3個あれば表現可能そうだけど // a < b < c // これだとどれかの2つが同じになって単調になりそう // a,b,c // a,(b+c)/2 // (1/2,1/4,1/4) (0,1/2,1/2) // (1/2,1/4,1/4) (1/4,3/8,3/8) class Program { static void Main() { int n = ni(); long[][] co = nml(n); long O = 500000000000000000L; List ret = new List(); long lmin = O*2; int argmin = -1; for(int i = 0;i < n;i++){ long x = (co[0][0] + co[i][0]) / 2; long y = (co[0][1] + co[i][1]) / 2; long d = Math.Abs(x - O) + Math.Abs(y - O); if(d < lmin){ lmin = d; argmin = i; } } if(argmin > 0){ long x = (co[0][0] + co[argmin][0]) / 2; long y = (co[0][1] + co[argmin][1]) / 2; co[0][0] = co[argmin][0] = x; co[0][1] = co[argmin][1] = y; ret.Add(new int[]{0, argmin}); } long tx = O*2 - co[0][0]; long ty = O*2 - co[0][1]; // Console.WriteLine($"{tx} {ty}"); long[][] sco = co.OrderBy(c => c[0]).ToArray(); List tls = new List(); int p = 0, q = n-1; for(int i = 0;i < 4;i++){ List ls = new List(); for(int j = 0;j < 2;j++){ if(sco[p][2] == 0)p++; ls.Add(sco[p++]); } for(int j = 0;j < 2;j++){ if(sco[q][2] == 0)q--; ls.Add(sco[q--]); } double[] xs = new double[]{ Convert.ToDouble(ls[0][0]) - tx, Convert.ToDouble(ls[1][0]) - tx, Convert.ToDouble(ls[2][0]) - tx, Convert.ToDouble(ls[3][0]) - tx }; min = Double.PositiveInfinity; simulate(xs, 10, new List()); foreach(int ind in best){ long x = (ls[ind][0] + ls[ind+1][0]) / 2; long y = (ls[ind][1] + ls[ind+1][1]) / 2; ret.Add(new int[]{ Convert.ToInt32(ls[ind][2]), Convert.ToInt32(ls[ind+1][2]) }); ls[ind][0] = ls[ind+1][0] = x; ls[ind][1] = ls[ind+1][1] = y; } long mins = long.MaxValue; int larg = -1; for(int j = 0;j < 4;j++){ if(Math.Abs(ls[j][0] - tx) < mins){ mins = Math.Abs(ls[j][0] - tx); larg = j; } } tls.Add(ls[larg]); } // long[][] ysco = sco.OrderBy(c => Math.Abs(c[0] - tx)).ToArray(); // List ls2 = new List(); // for(int i = 0;i < n;i++){ // if(ysco[i][2] == 0)continue; // ls2.Add(ysco[i]); // if(ls2.Count == 4)break; // } // for(int j = 0;j < 4;j++){ // Console.WriteLine($"moya {ls2[j][0]} {ls2[j][1]} {ls2[j][2]}"); // } long[][] sls = tls.OrderBy(c => c[1]).ToArray(); double[] ys = new double[]{ Convert.ToDouble(sls[0][1]) - ty, Convert.ToDouble(sls[1][1]) - ty, Convert.ToDouble(sls[2][1]) - ty, Convert.ToDouble(sls[3][1]) - ty }; // foreach(double y in ys){ // Console.WriteLine(y); // } min = Double.PositiveInfinity; simulate(ys, int.Min(14, 49 - ret.Count), new List()); foreach(int ind in best){ long x = (sls[ind][0] + sls[ind+1][0]) / 2; long y = (sls[ind][1] + sls[ind+1][1]) / 2; ret.Add(new int[]{ Convert.ToInt32(sls[ind][2]), Convert.ToInt32(sls[ind+1][2]) }); sls[ind][0] = sls[ind+1][0] = x; sls[ind][1] = sls[ind+1][1] = y; } // Console.WriteLine(best.Count); // Console.WriteLine(best); // Console.WriteLine($"nyao"); // for(int j = 0;j < 4;j++){ // Console.WriteLine($"{sls[j][0]} {sls[j][1]} {sls[j][2]}"); // } int arg = -1; double vald = Double.PositiveInfinity; for(int i = 0;i < n;i++){ if(co[i][2] == 0)continue; double d = Math.Max(Math.Abs(co[i][0] - tx), Math.Abs(co[i][1] - ty)); if(d < vald){ vald = d; arg = i; } } // Console.WriteLine($"arg {arg} {vald}"); ret.Add(new int[]{0, (int)co[arg][2]}); Console.WriteLine(ret.Count); foreach(int[] r in ret){ Console.WriteLine($"{r[0]+1} {r[1]+1}"); } } static double min; static List best = new List(); static void simulate(double[] a, int rem, List route) { for(int i = 0;i < 4;i++){ if(Math.Abs(a[i]) < min){ min = Math.Abs(a[i]); best = new List(route); } } if(rem == 0)return; for(int i = 0;i < 3;i++){ if(a[i] == a[i+1])continue; double[] b = (double[])a.Clone(); double v = (b[i] + b[i+1]) / 2; b[i] = b[i+1] = v; route.Add(i); simulate(b, rem-1, route); route.RemoveAt(route.Count-1); } } static string ns() { return Console.ReadLine(); } static int ni() { return Convert.ToInt32(ns()); } static int[] na() { return ns().Split(' ').Select(int.Parse).ToArray(); } static long[] nal() { return ns().Split(' ').Select(long.Parse).ToArray(); } static long[][] nml(int n) { long[][] ret = new long[n][]; for (int i = 0; i < n; i++) { long[] f = nal(); ret[i] = new long[]{f[0], f[1], i}; } return ret; } }