macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let mut s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } pub trait ChangeMinMax { fn change_min(&mut self, v: Self) -> bool; fn change_max(&mut self, v: Self) -> bool; } impl ChangeMinMax for T { fn change_min(&mut self, v: T) -> bool { *self > v && { *self = v; true } } fn change_max(&mut self, v: T) -> bool { *self < v && { *self = v; true } } } struct Input { n: usize, cards: Vec<(i64, i64)>, } impl Input { fn read_input() -> Self { input! { n: usize, c: [(i64, i64); n], } let mut cards = vec![]; for (a, b) in c { let a = a - 500_000_000_000_000_000; let b = b - 500_000_000_000_000_000; cards.push((a, b)); } Input { n, cards } } } #[derive(Debug, Clone)] struct State { operations: Vec<(usize, usize)>, } impl State { fn new() -> Self { State { operations: vec![] } } fn calc_score(&self, input: &Input) -> i64 { let mut cards = input.cards.clone(); for &(a, b) in &self.operations { let x = (cards[a].0 + cards[b].0) / 2; let y = (cards[a].1 + cards[b].1) / 2; cards[a] = (x, y); cards[b] = (x, y); } let v1 = cards[0].0.abs(); let v2 = cards[0].1.abs(); let sum = ((v1 as f64 * v1 as f64) + (v2 as f64 * v2 as f64)).sqrt(); if sum == 0.0 { 2000050 - self.operations.len() as i64 } else { (2e6 - 1e5 * (sum as f64 + 1.0).log10()).floor() as i64 } } } fn main() { let input = Input::read_input(); let initial_solution = State::new(); let solution = annealing(&input, initial_solution, 0.95); println!("{}", solution.operations.len()); for (a, b) in solution.operations { println!("{} {}", a + 1, b + 1); } } fn annealing(input: &Input, initial_solution: State, duration: f64) -> State { let mut solution = initial_solution; let mut best_solution = solution.clone(); let mut current_score = solution.calc_score(input); let mut best_score = current_score; let init_score = current_score; let mut all_iter = 0; let mut valid_iter = 0; let mut accepted_count = 0; let mut update_count = 0; let mut rng = Xorshift::new(); let duration_inv = 1.0 / duration; let since = std::time::Instant::now(); let temp0 = 1e4; let temp1 = 1e2; let mut inv_temp = 1.0 / temp0; loop { all_iter += 1; if (all_iter & ((1 << 4) - 1)) == 0 { let time = (std::time::Instant::now() - since).as_secs_f64() * duration_inv; let temp = f64::powf(temp0, 1.0 - time) * f64::powf(temp1, time); inv_temp = 1.0 / temp; if time >= 1.0 { break; } } // 変形 let neigh_type = rng.rand(3); let mut new_state = solution.clone(); if neigh_type == 0 { if new_state.operations.len() >= 50 { continue; } let (i, j) = loop { let i = rng.rand(input.n as u64) as usize; let j = rng.rand(input.n as u64) as usize; if i != j { break (i, j); } }; let pos = rng.rand(solution.operations.len() as u64 + 1) as usize; new_state.operations.insert(pos, (i, j)); } else if neigh_type == 1 { if new_state.operations.is_empty() { continue; } let pos = rng.rand(solution.operations.len() as u64) as usize; new_state.operations.remove(pos); } else { if new_state.operations.len() < 2 { continue; } let (i, j) = loop { let i = rng.rand(new_state.operations.len() as u64) as usize; let j = rng.rand(new_state.operations.len() as u64) as usize; if i != j { break (i, j); } }; new_state.operations.swap(i, j); } // スコア計算 let new_score = new_state.calc_score(input); let score_diff = new_score - current_score; if score_diff >= 0 || rng.randf() < f64::exp(score_diff as f64 * inv_temp) { // 解の更新 solution = new_state; current_score = new_score; accepted_count += 1; if best_score.change_max(current_score) { best_solution = solution.clone(); update_count += 1; } } valid_iter += 1; } eprintln!("===== annealing ====="); eprintln!("init score : {}", init_score); eprintln!("score : {}", best_score); eprintln!("all iter : {}", all_iter); eprintln!("valid iter : {}", valid_iter); eprintln!("accepted : {}", accepted_count); eprintln!("updated : {}", update_count); eprintln!(""); best_solution } // https://qiita.com/hatoo@github/items/652b81e8e83b0680bc0a #[derive(Debug)] #[allow(dead_code)] pub struct Xorshift { seed: u64, } impl Xorshift { #[allow(dead_code)] pub fn new() -> Xorshift { Xorshift { seed: 0xf0fb588ca2196dac, } } #[allow(dead_code)] pub fn with_seed(seed: u64) -> Xorshift { Xorshift { seed: seed } } #[inline] #[allow(dead_code)] pub fn next(&mut self) -> u64 { self.seed = self.seed ^ (self.seed << 13); self.seed = self.seed ^ (self.seed >> 7); self.seed = self.seed ^ (self.seed << 17); self.seed } #[inline] #[allow(dead_code)] pub fn rand(&mut self, m: u64) -> u64 { self.next() % m } #[inline] #[allow(dead_code)] // 0.0 ~ 1.0 pub fn randf(&mut self) -> f64 { use std::mem; const UPPER_MASK: u64 = 0x3FF0000000000000; const LOWER_MASK: u64 = 0xFFFFFFFFFFFFF; let tmp = UPPER_MASK | (self.next() & LOWER_MASK); let result: f64 = unsafe { mem::transmute(tmp) }; result - 1.0 } }