package extra; import java.io.PrintWriter; import java.util.*; import java.util.function.*; public class N5020HC { static Scanner in; static PrintWriter out; static String INPUT = ""; static void solve() { int n = ni(); ab = new long[n][]; for(int i = 0;i < n;i++){ ab[i] = new long[]{nl(), nl()}; } final long O = 500000000000000000L; final int m = 50; // ToLongBiFunction score = (route, turn) -> { // long x = (ab[0][0]-O)/(1L< score = route -> { long x = ab[0][0], y = ab[0][1]; for(int r : route){ x = (x + ab[r+1][0]) / 2; y = (y + ab[r+1][1]) / 2; } return O - Math.max(Math.abs(x-O), Math.abs(y-O)); }; Random gen = new Random(); // Result res = bogo(score, () -> { // int[] route = new int[m]; // for(int i = 0;i < m;i++){ // route[i] = gen.nextInt(44)+1; // } // return route; // }, 800); Result res = doOnepointHillClimbing(score, 44, m, new int[m], 800L, new SplittableRandom()); // tr(res.score); out.println(m); for(int r : res.route){ // out.println(1 + " " + (r+1)); out.println(1 + " " + (r+2)); } } static long[][] ab; static class Result { int[] route; long score; Result(int[] route, long score) { this.route = route; this.score = score; } } public static Result doBeamSearch(ToLongFunction score, Predicate isValid, int limval, int len, int W) { PriorityQueue beam = new PriorityQueue<>(Comparator.comparingLong(x -> x.score)); beam.add(new Result(new int[0], score.applyAsLong(new int[0]))); for(int i = 0;i < len;i++){ PriorityQueue nbeam = new PriorityQueue<>(Comparator.comparingLong(x -> x.score)); for(Result d : beam){ for(int k = 0;k < limval;k++){ int[] nroute = Arrays.copyOf(d.route, d.route.length+1); nroute[nroute.length-1] = k; if(isValid.test(nroute)){ long s = score.applyAsLong(nroute); if(!nbeam.isEmpty() && s <= nbeam.peek().score)continue; nbeam.add(new Result(nroute, s)); if(nbeam.size() > W)nbeam.poll(); } } } beam = nbeam; } while(beam.size() > 1)beam.poll(); Result last = beam.poll(); assert last != null; return new Result(last.route, last.score); } public static Result doOnepointAnnealing(ToLongFunction score, int limval, int len, int[] initial, long tl, SplittableRandom gen, double iniT, double M) { long S = System.currentTimeMillis(); assert initial.length == len; int[] cur = Arrays.copyOf(initial, len); long curscore = score.applyAsLong(cur); int[] argbest = Arrays.copyOf(cur, len); long best = curscore; double T = iniT; int rep = 0; while(System.currentTimeMillis() - S < tl){ int ind = gen.nextInt(len); int val = gen.nextInt(limval); int bak = cur[ind]; cur[ind] = val; if(val == bak)continue; long nexscore = score.applyAsLong(cur); if(nexscore >= curscore || gen.nextDouble() < Math.exp((nexscore - curscore) / T)){ curscore = nexscore; if(curscore > best){ best = curscore; argbest = Arrays.copyOf(cur, len); } }else{ cur[ind] = bak; } T *= M; rep++; } return new Result(argbest, best); } public static Result doOnepointHillClimbing(ToLongFunction score, int limval, int len, int[] initial, long tl, SplittableRandom gen) { long S = System.currentTimeMillis(); assert initial.length == len; int[] cur = Arrays.copyOf(initial, len); long curscore = score.applyAsLong(cur); int rep = 0; int updated = 0; while(System.currentTimeMillis() - S < tl){ int ind = gen.nextInt(len); int val = gen.nextInt(limval); int bak = cur[ind]; cur[ind] = val; if(val == bak)continue; long nexscore = score.applyAsLong(cur); if(nexscore >= curscore){ curscore = nexscore; updated++; }else{ cur[ind] = bak; } rep++; } // tr(rep, updated); return new Result(cur, curscore); } /** * greedyの判定用スコアに、そこからさらにgreedyした場合の最終スコアを採用する * O((limval*len)^2*score) * @param score * @param isValid * @param limval * @param len * @return */ public static Result richGreedy(ToLongBiFunction score, BiPredicate isValid, int limval, int len) { int[] route = new int[len]; for(int i = 1;i <= len;i++){ long max = Long.MIN_VALUE; int arg = -1; for(int v = 0;v < limval;v++){ route[i-1] = v; if(isValid.test(route, i)){ Result res = greedy(score, isValid, limval, len, i, route); if(res.score > max){ max = res.score; arg = v; } } } route[i-1] = arg; } long s = score.applyAsLong(route, len); return new Result(route, s); } public static Result greedy(ToLongBiFunction score, BiPredicate isValid, int limval, int len) { int[] route = new int[len]; return greedy(score, isValid, limval, len, 0, route); } /** * 各フェーズでスコアを最大化するものを採用 * O(limval*len*score) * @param score * @param isValid * @param limval * @param len * @param start * @return */ public static Result greedy(ToLongBiFunction score, BiPredicate isValid, int limval, int len, int start, int[] route) { for(int i = start + 1;i <= len;i++){ long max = Long.MIN_VALUE; int arg = -1; for(int v = 0;v < limval;v++){ route[i-1] = v; if(isValid.test(route, i)){ long ls = score.applyAsLong(route, i); if(ls > max){ max = ls; arg = v; } } } route[i-1] = arg; } long s = score.applyAsLong(route, len); return new Result(route, s); } /** * 時間まで列をランダム生成 * @param score * @param supplier * @param tl * @return */ public static Result bogo(ToLongFunction score, Supplier supplier, long tl) { long S = System.currentTimeMillis(); long best = Long.MIN_VALUE; int[] arg = null; while(System.currentTimeMillis() - S < tl){ int[] route = supplier.get(); long s = score.applyAsLong(route); if(s > best){ best = s; arg = route; } } return new Result(arg, best); } public static void main(String[] args) throws Exception { in = INPUT.isEmpty() ? new Scanner(System.in) : new Scanner(INPUT); out = new PrintWriter(System.out); solve(); out.flush(); } static int ni() { return Integer.parseInt(in.next()); } static long nl() { return Long.parseLong(in.next()); } static double nd() { return Double.parseDouble(in.next()); } static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); } }