結果

問題 No.5009 Draw A Convex Polygon
ユーザー akakimidoriakakimidori
提出日時 2022-12-02 00:19:05
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 972 ms / 2,600 ms
コード長 1,286 bytes
コンパイル時間 1,049 ms
実行使用メモリ 37,424 KB
スコア 1,000,000
平均クエリ数 1000001.00
最終ジャッジ日時 2022-12-02 00:19:10
合計ジャッジ時間 3,646 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 972 ms
37,424 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::Write;

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, (0, 1000000000));
    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