結果

問題 No.3154 convex polygon judge
ユーザー Kana Nagata
提出日時 2025-05-24 18:34:07
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 44 ms / 2,000 ms
コード長 3,779 bytes
コンパイル時間 12,131 ms
コンパイル使用メモリ 391,876 KB
実行使用メモリ 15,008 KB
最終ジャッジ日時 2025-05-24 18:34:24
合計ジャッジ時間 14,701 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

use convex_hull::convex_hull;
use proconio::input;

fn main() {
    input! {
        n: usize,
    }
    let points = {
        let mut points = Vec::with_capacity(n);
        for _ in 0..n {
            input! { x: i64, y: i64 }
            points.push([x, y]);
        }
        points
    };
    let hull = convex_hull(&points);
    let ans = hull.len() == n;
    println!("{}", if ans { "Yes" } else { "No" });
}

// convex_hull {{{
// https://ngtkana.github.io/ac-adapter-rs/convex_hull/index.html

#[allow(dead_code)]
mod convex_hull {
    type Point = [i64; 2];
    pub fn sqmag(p0: Point, p1: Point) -> i64 {
        let [x0, y0] = p0;
        let [x1, y1] = p1;
        let dx = x0 - x1;
        let dy = y0 - y1;
        dx * dx + dy * dy
    }
    pub fn ccw(p0: Point, p1: Point, p2: Point) -> i64 {
        let [x0, y0] = p0;
        let [x1, y1] = p1;
        let [x2, y2] = p2;
        (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0)
    }
    // det(p1 - p0, p3 - p2) を求めます。
    fn general_ccw(p0: Point, p1: Point, p2: Point, p3: Point) -> i64 {
        let [x0, y0] = p0;
        let [x1, y1] = p1;
        let [x2, y2] = p2;
        let [x3, y3] = p3;
        (x1 - x0) * (y3 - y2) - (x3 - x2) * (y1 - y0)
    }
    pub fn convex_hull(a: &[[i64; 2]]) -> Vec<[i64; 2]> {
        if a.is_empty() {
            Vec::new()
        } else if a.len() == 1 {
            vec![a[0]]
        } else if a.len() == 2 {
            if a[0] == a[1] {
                vec![a[0]]
            } else {
                vec![a[0], a[1]]
            }
        } else {
            let mut a = a.to_vec();
            a.sort_unstable();
            a.dedup();
            let mut hull = Vec::new();
            for &p in &a {
                while 2 <= hull.len() && 0 <= ccw(hull[hull.len() - 2], hull[hull.len() - 1], p) {
                    hull.pop();
                }
                hull.push(p);
            }
            let mid_len = hull.len();
            for &p in a.iter().rev().skip(1) {
                while mid_len < hull.len()
                    && 0 <= ccw(hull[hull.len() - 2], hull[hull.len() - 1], p)
                {
                    hull.pop();
                }
                hull.push(p);
            }
            if hull.first().unwrap() == hull.first().unwrap() {
                hull.pop();
            }
            hull
        }
    }
    pub fn caliper(a: &[[i64; 2]]) -> (i64, [[i64; 2]; 2]) {
        assert!(!a.is_empty());
        let a = convex_hull(a);
        if a.len() == 1 {
            (0, [a[0], a[0]])
        } else if a.len() == 2 {
            (sqmag(a[0], a[1]), [a[0], a[1]])
        } else {
            let n = a.len();
            let mut d = 0;
            let mut ans_i = usize::MAX;
            let mut ans_j = usize::MAX;
            let min_position = (0..n).min_by_key(|&i| a[i][0]).unwrap();
            let max_position = (0..n).max_by_key(|&i| a[i][0]).unwrap();
            let start_i = min_position.min(max_position);
            let start_j = min_position.max(max_position);
            let mut i = start_i;
            let mut j = start_j;
            while i != start_i + n && j != start_j + n {
                if 0 < general_ccw(a[(i + 1) % n], a[i % n], a[(j + 1) % n], a[j % n]) {
                    i += 1;
                } else {
                    j += 1;
                }
                let e = sqmag(a[i % n], a[j % n]);
                if d < e {
                    d = e;
                    ans_i = i;
                    ans_j = j;
                }
            }
            (d, [a[ans_i % n], a[ans_j % n]])
        }
    }
    pub fn is_convex(a: &[[i64; 2]]) -> bool {
        a.len() <= 2 || (0..a.len() - 2).all(|i| ccw(a[i], a[i + 1], a[i + 2]) < 0)
    }
}
// }}}
0