C++/Rust解答例 最古の遺跡 - 日本情報オリンピック2007本選より第三項

備忘録 C++に慣れたい
Rustでの解説が見当たらなかったのであわせて。

問題の概要

https://atcoder.jp/contests/joi2007ho/tasks/joi2007ho_c
与えられたn個の座標から4つを結んで出来る正方形のうち、面積が最大となる物の面積を出力する。

制約

• 
• 

入力

1行目に座標の個数、2行目以降には個の座標が座標がそれぞれ空白区切りで入力される。

解き方

高校数学のベクトルを理解してれば解ける
詳しい解き方は調べればいくらでも出てくるのでざっくりと

4点を全列挙すると計算量は。なのでまずTLE。
そこで、2つの座標を列挙し、正方形を成す残りの2点を探索する。
に垂直かつ同じ長さのを求め、このが存在するか確認。
正方形の向きが二つあるが、これは片方で良い。逆方向にが存在する場合、これは2点の組み合わせのうちに含まれる。
を二辺とする三角形と考えると、直角になるので三平方の定理からであり、今回の場合は正方形なのでこれがそのまま面積となる。

サンプルコード

ちょっと長いので折りたたみ

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<vector<int>> pillar(n, vector<int>(2));
  for (int i = 0; i < n; i++) {
    cin >> pillar[i][0] >> pillar[i][1];
  }
  sort(pillar.begin(), pillar.end());

  int ans = 0;

  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      int xi, yi; xi = pillar[i][0], yi = pillar[i][1];
      int xj, yj; xj = pillar[j][0], yj = pillar[j][1];
      int xdif, ydif; xdif = xj - xi, ydif = yj - yi;

      vector<int> p1(2);
      p1[0] = xi + ydif, p1[1] = yi - xdif;

      if (binary_search(pillar.begin(), pillar.end(), p1)) {
        vector<int> p2(2);
        p2[0] = xj + ydif, p2[1] = yj - xdif;
        if (binary_search(pillar.begin(), pillar.end(), p2)) {
          ans = max(ans, xdif * xdif + ydif * ydif);
        }
      }
    }
  }
  cout << ans << endl;
}

Rust

use std::cmp::max;
use std::io;

fn readstdin() -> String {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    input
}

fn split(v: String) -> Vec<i32> {
    v.split_whitespace()
        .map(|n| i32::from_str_radix(n, 10).unwrap())
        .collect()
}

fn main() {
    let n: usize = readstdin().trim().parse().unwrap();
    let mut pillar: Vec<Vec<i32>> = Vec::new();
    for _ in 0..n {
        pillar.push(split(readstdin()))
    }
    pillar.sort();

    let mut ans: i32 = 0;

    for i in 0..n {
        for j in i + 1..n {
            let (xi, yi) = (pillar[i][0], pillar[i][1]);
            let (xj, yj) = (pillar[j][0], pillar[j][1]);
            let (xdiff, ydiff) = (xj - xi, yj - yi);

            let p1 = vec![xi + ydiff, yi - xdiff];

            if pillar.binary_search(&p1).is_ok() {
                let p2 = vec![xj + ydiff, yj - xdiff];
                if pillar.binary_search(&p2).is_ok() {
                    ans = max(ans, xdiff * xdiff + ydiff * ydiff);
                }
            }
        }
    }
    println!("{}", ans)
}

コードの部分解説

どちらも基本的に同じ。
ただrustについては入力受けるだけでも長いので、そこだけ別関数。
今回はの探索に二分探索を使いたいのでソート。
rustのbinary_search()はResult型を返すので、ちゃんとis_ok()やis_err()を付ける。
変数p1, p2()について、p2をifの中に入れると少しだけ計算回数が減る。

もっと良いやりかたはあるだろうけど、まあACだし処理時間も短めだからいいかな。