macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let 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") }; } #[allow(unused)] #[inline] fn get_time()->f64{ static mut START:f64=-1.; let t=std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_secs_f64(); unsafe{ if START<0.{START=t;} t-START } } #[cfg(local)] #[allow(unused)] macro_rules! debug{ ()=>{ eprintln!(); }; ($x:literal)=>{ eprintln!("{:?}",$x); }; ($x:expr)=>{ eprintln!("{}: {:?}",stringify!($x),$x); }; ($x:literal,$($l:expr),*)=>{ eprint!("{:?}, ",$x); debug!($($l),*); }; ($x:expr,$($l:expr),*)=>{ eprint!("{}: {:?}, ",stringify!($x),$x); debug!($($l),*); } } #[cfg(not(local))] #[allow(unused)] macro_rules! debug{ ($($_:expr),*)=>{} } #[allow(unused)] mod rnd { static mut S:usize=88172645463325252; #[inline] pub fn next()->usize{ unsafe{ S^=S<<7; S^=S>>9; S } } #[inline] pub fn nextf()->f64{ unsafe{ std::mem::transmute::<_,f64>(0x3ff0000000000000|next()&0xfffffffffffff)-1. } } // [a,b) #[inline] pub fn range(a:usize,b:usize)->usize{ next()%(b-a)+a } #[inline] pub fn shuffle(list:&mut [T]){ for i in (0..list.len()).rev(){ list.swap(i,next()%(i+1)); } } #[inline] pub fn exu(a:usize,b:usize,skip:usize)->usize{ let ret=range(a,b-1); if ret==skip{b-1} else{ret} } #[inline] pub fn rangei(a:i64,b:i64)->i64{ (next()>>1) as i64%(b-a)+a } } #[inline] fn d(p1:(usize,usize),p2:(usize,usize))->i64{ let y=p1.0-p2.0; let x=p1.1-p2.1; (y*y+x*x) as i64 } const N:usize=100; const M:usize=8; const A:usize=5; struct In{ pos:[(usize,usize);N] } impl In{ #[inline] fn input()->In{ input!{ n:usize, m:usize, tp:[(usize,usize);n] } assert_eq!((n,m),(N,M)); let mut it=tp.into_iter(); let mut pos=[(!0,!0);N]; pos.fill_with(||it.next().unwrap()); In{pos} } } #[derive(Clone,Copy,Default)] struct Edge{ dir:i64, tp:[i64;M], best:i64 } impl Edge{ #[inline] fn new(input:&In,a:usize,b:usize,m:&[(usize,usize);M])->Edge{ let dir=A as i64*A as i64*d(input.pos[a],input.pos[b]); let mut best=dir; let mut tp=[-1;M]; for i in 0..M{ tp[i]=A as i64*(d(input.pos[a],m[i])+d(m[i],input.pos[b])); best=best.min(tp[i]); } Edge{dir,tp,best} } #[inline] fn change(&mut self,input:&In,a:usize,b:usize,idx:usize,np:(usize,usize))->bool{ let new_dist=A as i64*(d(input.pos[a],np)+d(np,input.pos[b])); let back=self.tp[idx]; self.tp[idx]=new_dist; if self.best>new_dist{ self.best=new_dist; true } else if back==self.best{ self.best=self.dir; for i in 0..M{ self.best=self.best.min(self.tp[i]); } false } else{ false } } } #[derive(Clone)] struct Out{ m:[(usize,usize);M], route:[usize;N+1], dist:[[Edge;N];N] } impl Out{ #[inline] fn new(input:&In)->Out{ let mut route=[!0;N+1]; let mut it=0..; route.fill_with(||it.next().unwrap()); route[N]=0; rnd::shuffle(&mut route[1..N]); let mut m=[(!0,!0);M]; for i in &mut m{ *i=(rnd::next()%1001,rnd::next()%1001); } let mut dist=[[Default::default();N];N]; for i in 0..N{ for j in 0..N{ dist[i][j]=Edge::new(input,i,j,&m); } } Out{m,route,dist} } #[inline] fn score(&self)->i64{ let mut ret=0; for w in self.route.windows(2){ ret+=self.dist[w[0]][w[1]].best; } ret } #[inline] fn try_opt2(&self,a:usize,b:usize)->i64{ // assert!(1<=a.min(b) && a.min(b)+1b{ std::mem::swap(&mut a,&mut b); } self.route[a..b].reverse(); } } fn hc(out:&mut Out,it:usize){ const T:f64=10000.; for i in 0..it{ let heat=T*(1.-i as f64/it as f64); let a=rnd::range(1,N); let mut b; while{ b=rnd::range(1,N); a-b+1<=2 }{} let diff=out.try_opt2(a,b); if (-heat*rnd::nextf().ln()) as i64>=diff{ out.opt2(a,b); } } } fn sa(input:&In)->Out{ let mut cur=Out::new(input); let mut score=cur.score(); let mut best=score; let mut iter=0; let mut up=0; while get_time()<0.98{ let back=cur.clone(); let a=rnd::next()&7; let p=cur.m[a]; let mut np; while{ np=(p.0+rnd::rangei(-100,100) as usize,p.1+rnd::rangei(-100,100) as usize); !(np.0<=1000 && np.1<=1000) }{} // let np=(rnd::next()%1001,rnd::next()%1001); cur.m[a]=np; for i in 0..N{ for j in 0..N{ cur.dist[i][j].change(input,i,j,a,np); } } iter+=1; hc(&mut cur,500); let new_score=cur.score(); if score>=new_score{ score=new_score; up+=1; best=best.min(score); } else{ cur=back; } } let p=up as f64/iter as f64; debug!(iter,p); debug!(score,best); assert_eq!(score,cur.score()); // println!("{}",score); cur } fn main(){ let input=In::input(); let out=sa(&input); for (a,b) in &out.m{ println!("{a} {b}"); } let mut route=vec![(1,1)]; for w in out.route.windows(2){ let edge=out.dist[w[0]][w[1]]; if edge.dir!=edge.best{ let mut t=!0; for (i,&m) in edge.tp.iter().enumerate(){ if m==edge.best{ t=i; break; } } route.push((2,t+1)); } route.push((1,w[1]+1)); } println!("{}",route.len()); for (t,v) in route{ println!("{t} {v}"); } }