結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー ainem-m
提出日時 2023-04-27 09:56:33
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 4,302 bytes
コンパイル時間 2,526 ms
コンパイル使用メモリ 138,468 KB
実行使用メモリ 4,372 KB
スコア 4,521,707
最終ジャッジ日時 2023-04-27 09:56:38
合計ジャッジ時間 4,615 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

const INF: i64 = 1000000000;

/// 作問者terry_u16さんの提出から頂いた
/// 入力受け取り用のマクロ
macro_rules! get {
      ($t:ty) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.trim().parse::<$t>().unwrap()
          }
      };
      ($($t:ty),*) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              let mut iter = line.split_whitespace();
              (
                  $(iter.next().unwrap().parse::<$t>().unwrap(),)*
              )
          }
      };
      ($t:ty; $n:expr) => {
          (0..$n).map(|_|
              get!($t)
          ).collect::<Vec<_>>()
      };
      ($($t:ty),*; $n:expr) => {
          (0..$n).map(|_|
              get!($($t),*)
          ).collect::<Vec<_>>()
      };
      ($t:ty ;;) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.split_whitespace()
                  .map(|t| t.parse::<$t>().unwrap())
                  .collect::<Vec<_>>()
          }
      };
      ($t:ty ;; $n:expr) => {
          (0..$n).map(|_| get!($t ;;)).collect::<Vec<_>>()
      };
}

/// Rustでは入力から受け取った変数を
/// グローバルに定義することが難しいので
/// 構造体として持つと便利
#[allow(dead_code)]
#[derive(Debug, Clone)]
struct Input {
    n: usize,
    m: usize,
    points: Vec<Point>,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
struct Point {
    x: i32,
    y: i32,
}

impl Point {
    fn new(x: i32, y: i32) -> Self {
        Self { x, y }
    }
    fn dist_sq(&self, other: &Self) -> i64 {
        let dx = self.x - other.x;
        let dy = self.y - other.y;
        (dx * dx + dy * dy) as i64
    }
}

fn main() {
    let input = read_input();
    let mut points = input.points.clone();
    //     宇宙ステーションの座標は適当に決め打ち
    //
    //   x  x  x
    //   x     x
    //   x  x  x
    //
    // みたいにする
    points.push(Point::new(300, 300));
    points.push(Point::new(300, 500));
    points.push(Point::new(300, 700));
    points.push(Point::new(500, 300));
    points.push(Point::new(500, 700));
    points.push(Point::new(700, 300));
    points.push(Point::new(700, 500));
    points.push(Point::new(700, 700));

    // 経路の作成（貪欲法）

    // 惑星1から出発し、一番近い惑星を貪欲に選び続ける（Nearest Neighbour法）
    let mut v = 0;
    let mut visited = vec![false; input.n];
    visited[0] = true;
    let mut route = vec![0];

    // 惑星1以外のN-1個の惑星を訪問していく
    for _ in 0..input.n - 1 {
        let mut nearest_dist = INF;
        let mut nearest_v = None;

        // 一番近い惑星を探す
        for next in 0..input.n {
            if visited[next] {
                continue;
            }

            let d = calc_energy(&input, &points, v, next);
            if d < nearest_dist {
                nearest_dist = d;
                nearest_v = Some(next);
            }
        }
        v = nearest_v.unwrap();
        visited[v] = true;
        route.push(nearest_v.unwrap());
    }
    route.push(0);

    // 解の出力

    // 宇宙ステーションの座標を出力
    for Point { x, y } in points.iter().skip(input.n) {
        println!("{x} {y}");
    }

    // 経路の長さを出力
    println!("{}", route.len());

    // 経路を出力
    for v in route {
        if v < input.n {
            println!("1 {}", v + 1);
        } else {
            println!("2 {}", v - input.n + 1);
        }
    }
}

/// 入力読み込み
fn read_input() -> Input {
    let (n, m) = get!(usize, usize);

    let mut points = vec![];

    for _ in 0..n {
        let (x, y) = get!(i32, i32);
        points.push(Point::new(x, y));
    }

    Input { n, m, points }
}

/// エネルギー計算
fn calc_energy(input: &Input, points: &Vec<Point>, i: usize, j: usize) -> i64 {
    let mut energy = points[i].dist_sq(&points[j]);
    if i < input.n {
        energy *= 5;
    }
    if j < input.n {
        energy *= 5;
    }
    energy
}
0