#include #include #include #include struct timeval tt; double beg, cur; #define MT_N 624 #define MT_M 397 #define MT_MATRIX_A 0x9908b0dfUL #define MT_UPPER_MASK 0x80000000UL #define MT_LOWER_MASK 0x7fffffffUL static unsigned int mt[MT_N]; static int mti = MT_N + 1; void init_genrand(unsigned int s) { mt[0] = s & 0xffffffffUL; for (mti = 1; mti < MT_N; mti++) { mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti); mt[mti] &= 0xffffffffUL; } } unsigned int genrand() { unsigned int y; static unsigned int mag01[2] = {0x0UL, MT_MATRIX_A}; if (mti >= MT_N) { int kk; if (mti == MT_N + 1) init_genrand(5489UL); for (kk = 0; kk < MT_N - MT_M; kk++) { y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK); mt[kk] = mt[kk+MT_M] ^ (y >> 1) ^ mag01[y&0x1UL]; } for (; kk < MT_N - 1; kk++) { y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK); mt[kk] = mt[kk+(MT_M-MT_N)] ^ (y >> 1) ^ mag01[y&0x1UL]; } y = (mt[MT_N-1] & MT_UPPER_MASK) | (mt[0] & MT_LOWER_MASK); mt[MT_N-1] = mt[MT_M-1] ^ (y >> 1) ^ mag01[y&0x1UL]; mti = 0; } y = mt[mti++]; y ^= (y >> 11); y ^= (y << 7) & 0x9d2c5680UL; y ^= (y << 15) & 0xefc60000UL; y ^= (y >> 18); return y; } void shuffle_permutation(int N, int p[], int K) { int i, j; while (K--) { i = genrand() % N + 1; j = genrand() % N + 1; if (i != j) { p[i] ^= p[j]; p[j] ^= p[i]; p[i] ^= p[j]; } } } void chmax(long long *a, long long b) { if (*a < b) *a = b; } const long long THR = 500000000000000000LL; int score(int N, long long AA[], long long BB[], int K, int move[][2]) { static int i, j, k; static long long A[46], B[46], tmp; for (i = 1; i <= N; i++) { A[i] = AA[i]; B[i] = BB[i]; } for (k = 1; k <= K; k++) { i = move[k][0]; j = move[k][1]; tmp = (A[i] + A[j]) / 2; A[i] = tmp; A[j] = tmp; tmp = (B[i] + B[j]) / 2; B[i] = tmp; B[j] = tmp; } // printf("%lld %lld\n", A[1], B[1]); tmp = llabs(A[1] - THR); chmax(&tmp, llabs(B[1] - THR)); return (int)(2000000 - 100000 * log10(tmp + 1.0)); } long long optimal_triangle_score(int N, long long AA[], long long BB[]) { static int ii, jj; static long long tmp, min; min = THR * 3 + 10; for (ii = 2; ii <= N; ii++) { for (jj = ii + 1; jj <= N; jj++) { tmp = llabs(AA[1] + AA[ii] + AA[jj] - THR * 3 - 10); chmax(&tmp, llabs(BB[1] + BB[ii] + BB[jj] - THR * 3 - 10)); if (min > tmp) min = tmp; } } return min; } int optimal_triangle_playout(int N, long long AA[], long long BB[], int K, int move[][2]) { static int i, j, k, ii, jj, argmin[2]; static long long A[4], B[4], tmp, min; min = THR * 3 + 10; for (ii = 2; ii <= N; ii++) { for (jj = ii + 1; jj <= N; jj++) { tmp = llabs(AA[1] + AA[ii] + AA[jj] - THR * 3 - 10); chmax(&tmp, llabs(BB[1] + BB[ii] + BB[jj] - THR * 3 - 10)); if (min > tmp) { min = tmp; argmin[0] = ii; argmin[1] = jj; } } } ii = argmin[0]; jj = argmin[1]; A[1] = AA[1]; B[1] = BB[1]; A[2] = AA[ii]; B[2] = BB[ii]; A[3] = AA[jj]; B[3] = BB[jj]; for (k = 1, i = 1, j = 2; k <= K; k++, j ^= 1) { tmp = (A[i] + A[j]) / 2; A[i] = tmp; A[j] = tmp; tmp = (B[i] + B[j]) / 2; B[i] = tmp; B[j] = tmp; move[k][0] = 1; move[k][1] = (j == 2)? ii: jj; } tmp = llabs(A[1] - THR); chmax(&tmp, llabs(B[1] - THR)); min = tmp; if (K > 1) { A[1] = AA[1]; B[1] = BB[1]; A[2] = (AA[ii] + AA[jj]) / 2; B[2] = (BB[ii] + BB[jj]) / 2; A[3] = A[2]; B[3] = B[2]; for (k = 2, i = 1, j = 2; k <= K; k++, j ^= 1) { tmp = (A[i] + A[j]) / 2; A[i] = tmp; A[j] = tmp; tmp = (B[i] + B[j]) / 2; B[i] = tmp; B[j] = tmp; } tmp = llabs(A[1] - THR); chmax(&tmp, llabs(B[1] - THR)); if (min > tmp) { move[1][0] = ii; move[1][1] = jj; for (k = 2, j = 2; k <= K; k++, j ^= 1) { move[k][0] = 1; move[k][1] = (j == 2)? ii: jj; } } } return (int)(2000000 - 100000 * log10(min + 1.0)); } int random_optimal_triangle_playout(int N, long long AA[], long long BB[], int K, int move[][2]) { static int i, j, k, r, ans, tmp_ans, tmp_move[51][2]; static long long A[46], B[46], tmp; ans = optimal_triangle_playout(N, AA, BB, K, move); while (1) { gettimeofday(&tt, NULL); cur = tt.tv_sec + (double)tt.tv_usec / 1000000; if (cur - beg > 0.99) break; for (i = 1; i <= N; i++) { A[i] = AA[i]; B[i] = BB[i]; } r = genrand() % 21 + 5; for (k = 1; k <= r; k++) { do { i = genrand() % N + 1; j = genrand() % N + 1; } while (i == j); tmp = (A[i] + A[j]) / 2; A[i] = tmp; A[j] = tmp; tmp = (B[i] + B[j]) / 2; B[i] = tmp; B[j] = tmp; tmp_move[k][0] = i; tmp_move[k][1] = j; } tmp_ans = optimal_triangle_playout(N, A, B, K - r, tmp_move[r]); if (ans < tmp_ans) { ans = tmp_ans; for (k = 1; k <= K; k++) { move[k][0] = tmp_move[k][0]; move[k][1] = tmp_move[k][1]; } } } return ans; } int greedy_optimal_triangle_playout(int N, long long AA[], long long BB[], int K, int move[][2]) { static int i, j, k, ii, jj, ans, tmp_ans, tmp_move[51][2]; static long long A[46], B[46], tmp, tmpp[2][2], min, tmp_min; ans = optimal_triangle_playout(N, AA, BB, K, move); for (i = 1; i <= N; i++) { A[i] = AA[i]; B[i] = BB[i]; } for (k = 1, ii = 0, jj = 0; k <= K; k++) { tmp_min = optimal_triangle_score(N, A, B); for (i = 1, min = tmp_min; i <= N; i++) { for (j = i + 1; j <= N; j++) { if (i == ii && j == jj) continue; tmpp[0][0] = A[i]; tmpp[0][1] = A[j]; tmpp[1][0] = B[i]; tmpp[1][1] = B[j]; tmp = (A[i] + A[j]) / 2; A[i] = tmp; A[j] = tmp; tmp = (B[i] + B[j]) / 2; B[i] = tmp; B[j] = tmp; tmp = optimal_triangle_score(N, A, B); if (min > tmp) { min = tmp; tmp_move[k][0] = i; tmp_move[k][1] = j; } A[i] = tmpp[0][0]; A[j] = tmpp[0][1]; B[i] = tmpp[1][0]; B[j] = tmpp[1][1]; } } if (min == tmp_min) { do { i = genrand() % N + 1; j = genrand() % N + 1; } while (i == j); tmp_move[k][0] = i; tmp_move[k][1] = j; } ii = tmp_move[k][0]; jj = tmp_move[k][1]; tmp = (A[ii] + A[jj]) / 2; A[ii] = tmp; A[jj] = tmp; tmp = (B[ii] + B[jj]) / 2; B[ii] = tmp; B[jj] = tmp; tmp_ans = optimal_triangle_playout(N, A, B, K - k, tmp_move[k]); if (ans < tmp_ans) { ans = tmp_ans; for (i = 1; i <= K; i++) { move[i][0] = tmp_move[i][0]; move[i][1] = tmp_move[i][1]; } } } return ans; } int random_greedy_optimal_triangle_playout(int N, long long AA[], long long BB[], int K, int move[][2]) { static int i, j, k, r, ans, tmp_ans, tmp_move[51][2]; static long long A[46], B[46], tmp; ans = greedy_optimal_triangle_playout(N, AA, BB, K, move); while (1) { gettimeofday(&tt, NULL); cur = tt.tv_sec + (double)tt.tv_usec / 1000000; if (cur - beg > 0.95) break; for (i = 1; i <= N; i++) { A[i] = AA[i]; B[i] = BB[i]; } r = genrand() % 11 + 10; for (k = 1; k <= r; k++) { do { i = genrand() % N + 1; j = genrand() % N + 1; } while (i == j); tmp = (A[i] + A[j]) / 2; A[i] = tmp; A[j] = tmp; tmp = (B[i] + B[j]) / 2; B[i] = tmp; B[j] = tmp; tmp_move[k][0] = i; tmp_move[k][1] = j; } tmp_ans = greedy_optimal_triangle_playout(N, A, B, K - r, tmp_move[r]); if (ans < tmp_ans) { ans = tmp_ans; for (k = 1; k <= K; k++) { move[k][0] = tmp_move[k][0]; move[k][1] = tmp_move[k][1]; } } } return ans; } int main() { gettimeofday(&tt, NULL); beg = tt.tv_sec + (double)tt.tv_usec / 1000000; int i, N; long long A[46], B[46]; scanf("%d", &N); for (i = 1; i <= N; i++) scanf("%lld %lld", &(A[i]), &(B[i])); int k = 50, ans, move[51][2]; // ans = random_optimal_triangle_playout(N, A, B, k, move); // ans = greedy_optimal_triangle_playout(N, A, B, k, move); ans = random_greedy_optimal_triangle_playout(N, A, B, k, move); // printf("%d\n", score(N, A, B, k, move)); printf("%d\n", k); for (i = 1; i <= k; i++) printf("%d %d\n", move[i][0], move[i][1]); fflush(stdout); return 0; }