use std::time::{SystemTime, Duration}; pub mod random { pub struct PcgXshRr { state: u64, } impl PcgXshRr { pub fn new(state: u64) -> Self { PcgXshRr { state, } } pub fn nextInt(&mut self) -> u32 { let oldstate = self.state; self.state = oldstate * 6364136223846793005u64 + 521u64; let xorshift : u32 = (((oldstate >> 18 ) ^ oldstate) >> 27) as u32 ; let rotation : u32 = (oldstate >> 59 ) as u32; return (xorshift >> rotation) | (xorshift << ((-1 * rotation as i32) & 31)); } pub fn gen(&mut self) -> u32 { return self.nextInt(); } pub fn nextDouble(&mut self) -> f64 { return (self.nextInt() as f64) * 0.00000000023283064365386963; // 1 / (1 << 32) } pub fn nextIntMod(&mut self, n: u32) -> u32 { // return (n as f64 * self.nextDouble()) as u32; return self.nextInt() % n; } } } fn main() { let start_time = get_time(); let mut rng = { let t = SystemTime::now() .duration_since(SystemTime::UNIX_EPOCH) .unwrap(); let seed = t.subsec_nanos() as u64 ^ 114514; random::PcgXshRr::new(seed) }; let n: usize = { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); line.trim().parse().unwrap() }; let mut a = vec![!0; n]; let mut b = vec![!0; n]; for i in 0..n { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); let mut nums = line.trim().split_whitespace().map(|x| x.parse::().unwrap()); let e = nums.next().unwrap(); let f = nums.next().unwrap(); a[i] = e; b[i] = f; } let mut solution = vec![]; for _ in 0..50 { let i = 0; let mut j = rng.gen() as usize % (n - 1); if j >= i { j += 1; } solution.push((i, j)); } let mut score = calculate_score(&solution, &a, &b); // Simulated Annealing let start_temperature = 1e4; let end_temperature = 1e-9; let mut temperature = start_temperature; let end_time = 0.95; let mut iterations = 0; let mut acs = 0; loop { iterations += 1; // Update time, temperature if (iterations & ((1 << 10) - 1)) == 0 { let time = get_time(); temperature = start_temperature + (end_temperature - start_temperature) * (time - start_time) / (end_time - start_time); if time > end_time { eprintln!("iterations:{:7}, ac:{:.02}%, score:{:7}", iterations, acs as f64 * 100.0 / iterations as f64, score); break; } } let random = rng.gen() as usize % 2; if random < 1 { let index = rng.gen() as usize % solution.len(); let (current_i, current_j) = solution[index]; let new_i = rng.gen() as usize % n; let mut new_j = rng.gen() as usize % (n - 1); if new_j >= new_i { new_j += 1; } solution[index] = (new_i, new_j); let before = score; let after = calculate_score(&solution, &a, &b); let delta_score = after - before; if delta_score <= 0 || rng.nextDouble() < (-delta_score as f64 / temperature).exp() { acs += 1; score += delta_score; } else { solution[index] = (current_i, current_j); } } else if random < 2 { let index1 = rng.gen() as usize % solution.len(); let mut index2 = rng.gen() as usize % (solution.len() - 1); if index2 >= index1 { index2 += 1; } { let swap = solution[index1]; solution[index1] = solution[index2]; solution[index2] = swap; } let before = score; let after = calculate_score(&solution, &a, &b); let delta_score = after - before; if delta_score <= 0 || rng.nextDouble() < (-delta_score as f64 / temperature).exp() { acs += 1; score += delta_score; } else { let swap = solution[index1]; solution[index1] = solution[index2]; solution[index2] = swap; } } } println!("{}", solution.len()); for i in 0..solution.len() { println!("{} {}", 1 + solution[i].0, 1 + solution[i].1); } } fn get_time() -> f64 { static mut STIME: f64 = -1.0; let t = SystemTime::now() .duration_since(SystemTime::UNIX_EPOCH) .unwrap(); let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9; unsafe { if STIME < 0.0 { STIME = ms; } ms - STIME } } fn calculate_score(solution: &Vec<(usize, usize)>, a0: &Vec, b0: &Vec) -> i64 { let mut a = a0.clone(); let mut b = b0.clone(); for k in 0..solution.len() { let (i, j) = solution[k]; let new_a = (a[i] + a[j]) >> 1; let new_b = (b[i] + b[j]) >> 1; a[i] = new_a; b[i] = new_b; a[j] = new_a; b[j] = new_b; } let v1 = (a[0] - 5e17 as i64).abs(); let v2 = (b[0] - 5e17 as i64).abs(); v1.max(v2) }