結果

問題 No.3154 convex polygon judge
コンテスト
ユーザー atcoder8
提出日時 2025-05-20 22:37:15
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 43 ms / 2,000 ms
コード長 1,133 bytes
コンパイル時間 23,140 ms
コンパイル使用メモリ 396,188 KB
実行使用メモリ 14,984 KB
最終ジャッジ日時 2025-05-20 22:37:47
合計ジャッジ時間 25,337 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::input;

type Coord = (i64, i64);

fn main() {
    println!("{}", if solve() { "Yes" } else { "No" });
}

fn solve() -> bool {
    input! {
        n: usize,
        xy: [(i64, i64); n],
    }

    let pivot_coord = *xy.iter().min().unwrap();

    let mut sorted_xy = xy
        .iter()
        .cloned()
        .filter(|&coord| coord != pivot_coord)
        .collect::<Vec<_>>();
    sorted_xy.sort_unstable_by(|&coord1, &coord2| compare_angle(pivot_coord, coord1, coord2));

    let mut stack = vec![pivot_coord];
    for &coord in sorted_xy.iter().chain(&[pivot_coord]) {
        if stack.len() >= 2 {
            if compare_angle(stack[stack.len() - 2], stack[stack.len() - 1], coord).is_ge() {
                return false;
            }
        }

        stack.push(coord);
    }

    true
}

fn calc_diff(from: Coord, to: Coord) -> Coord {
    (to.0 - from.0, to.1 - from.1)
}

fn compare_angle(pivot_coord: Coord, coord1: Coord, coord2: Coord) -> std::cmp::Ordering {
    let (dx1, dy1) = calc_diff(pivot_coord, coord1);
    let (dx2, dy2) = calc_diff(pivot_coord, coord2);
    (dx2 * dy1).cmp(&(dx1 * dy2))
}
0