結果

問題 No.5009 Draw A Convex Polygon
コンテスト
ユーザー akakimidori
提出日時 2022-12-02 00:12:46
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 1,402 bytes
コンパイル時間 1,213 ms
実行使用メモリ 38,564 KB
スコア 0
平均クエリ数 915619.00
最終ジャッジ日時 2022-12-02 00:12:54
合計ジャッジ時間 2,908 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: type alias is never used: `Map`
 --> Main.rs:4:1
  |
4 | type Map<K, V> = BTreeMap<K, V>;
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(dead_code)]` on by default

warning: type alias is never used: `Set`
 --> Main.rs:5:1
  |
5 | type Set<T> = BTreeSet<T>;
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: type alias is never used: `Deque`
 --> Main.rs:6:1
  |
6 | type Deque<T> = VecDeque<T>;
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: 3 warnings emitted

ソースコード

diff # 

use std::io::Write;
use std::collections::*;

type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;

fn main() {
    let n = 1000000;
    let mut dir = vec![];
    for s in 1..=1000 {
        for i in 1..=s {
            let j = s - i;
            if gcd(i, j) == 1 {
                dir.push((i, j));
                dir.push((-i, -j));
                dir.push((j, -i));
                dir.push((-j, i));
            }
        }
        if dir.len() > n {
            break;
        }
    }
    dir.truncate(n);
    sort_points_by_argument(&mut dir);
    dir.insert(0, (-1000000000, 0));
    for i in 1..dir.len() {
        let p = dir[i - 1];
        dir[i].0 += p.0;
        dir[i].1 += p.1;
    }
    dir.pop();
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    writeln!(out, "{}", dir.len()).ok();
    for (x, y) in dir {
        writeln!(out, "{} {}", x, y).ok();
    }
}

fn gcd(a: i64, b: i64) -> i64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

pub fn sort_points_by_argument(p: &mut [(i64, i64)]) {
    p.sort_by(|a, b| {
        (a.1 >= 0)
            .cmp(&(b.1 >= 0))
            .then_with(|| (!(a.0 >= 0 && a.1 >= 0)).cmp(&(!(b.0 >= 0 && b.1 >= 0))))
            .then_with(|| (*a != (0, 0)).cmp(&(*b != (0, 0))))
            .then_with(|| (a.1 * b.0).cmp(&(a.0 * b.1)))
    });
}
0