using System; 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]; long[][] sco = co.OrderBy(c => c[0]).ToArray(); 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[][] 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; } long[][] sls = ls2.OrderBy(c => c[1]).ToArray(); double[] ys = new double[]{ Convert.ToDouble(ls2[0][1]) - ty, Convert.ToDouble(ls2[1][1]) - ty, Convert.ToDouble(ls2[2][1]) - ty, Convert.ToDouble(ls2[3][1]) - ty }; min = Double.PositiveInfinity; simulate(ys, int.Min(14, 49 - ret.Count), new List()); foreach(int ind in best){ long x = (ls2[ind][0] + ls2[ind+1][0]) / 2; long y = (ls2[ind][1] + ls2[ind+1][1]) / 2; ret.Add(new int[]{ Convert.ToInt32(ls2[ind][2]), Convert.ToInt32(ls2[ind+1][2]) }); ls2[ind][0] = ls2[ind+1][0] = x; ls2[ind][1] = ls2[ind+1][1] = y; } 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; } } 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; } }