#835634 (Rust) No.199 星を描こう

• 問題: No.199 星を描こう
• ユーザー: PU
• 提出日時: 2023-01-26 23:42:43
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 6,931 bytes
• コンパイル時間: 12,753 ms
• コンパイル使用メモリ: 399,800 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-27 13:58:52
• 合計ジャッジ時間: 14,097 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 25

ソースコード

pub use input_helper::stdin_reader::*;

fn main() {
    let mut v: Vec<Point> = vec![];
    for _ in 0..5 {
        let (x, y): (f64, f64) = read_line();
        v.push(Point::new(x, y));
    }

    let ch = v.convex_hull();
    if ch.len() == 5 {
        println!("YES");
    } else {
        println!("NO");
    }
}

use std::ops::{Add, Sub};

#[derive(Debug, Copy, Clone, PartialEq, PartialOrd)]
struct Point {
    x: f64,
    y: f64,
}

impl Point {
    pub fn new<T: Into<f64>>(x: T, y: T) -> Self {
        Self {
            x: x.into(),
            y: y.into(),
        }
    }
}

impl Add for Point {
    type Output = Self;

    fn add(self, rhs: Self) -> Self {
        Self {
            x: self.x + rhs.x,
            y: self.y + rhs.y,
        }
    }
}

impl Sub for Point {
    type Output = Self;

    fn sub(self, rhs: Self) -> Self::Output {
        Self {
            x: self.x - rhs.x,
            y: self.y - rhs.y,
        }
    }
}

impl Point {
    /// 3D cross product of OA and OB vectors, (i.e. z-component of their
    /// 2D cross product, but remember that it is not defined in 2D).
    /// Return a positive value, if OAB makes a counter-clockwise turn,
    /// negative for clockwise turn, and zero if the points are collinear.
    pub fn cross_product(o: Self, a: Self, b: Self) -> f64 {
        (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)
    }
}

trait ConvexHull {
    type Output;
    fn convex_hull(&mut self) -> Self::Output;
}

impl ConvexHull for Vec<Point> {
    type Output = Self;
    /// 与えられた点集合の凸包を解きます。
    ///
    /// # 制約
    ///
    /// `self`が浮動小数点の集合の場合、NaNが含まれているとPanicします。
    ///
    /// # 注意
    ///
    /// この関数は`self`に対してソートや重複の削除などの破壊的変更を行います。
    fn convex_hull(&mut self) -> Self::Output {
        if self.len() <= 1 {
            return self.to_vec();
        }

        self.sort_by(|a, b| a.partial_cmp(b).unwrap());
        self.dedup();

        // Build loewr hull.
        let mut lower: Vec<Point> = vec![];
        for p in self.iter() {
            while lower.len() >= 2
                && Point::cross_product(lower[lower.len() - 2], lower[lower.len() - 1], *p) <= 0.0
            {
                lower.pop();
            }
            lower.push(*p);
        }

        // Build upper hull.
        let mut upper: Vec<Point> = vec![];
        for p in self.iter().rev() {
            while upper.len() >= 2
                && Point::cross_product(upper[upper.len() - 2], upper[upper.len() - 1], *p) <= 0.0
            {
                upper.pop();
            }
            upper.push(*p);
        }

        // Last point of each list is omitted because it is repeated
        // at the beginning of the other list.
        lower.pop();
        upper.pop();

        // Concatenation of the lower and upper hulls gives the convex hull.
        lower.append(&mut upper);

        lower
    }
}

#[test]
fn convex_hull_test() {
    let mut t: Vec<Point> = vec![];
    for i in 0..10 {
        for j in 0..10 {
            t.push(Point::new(i, j));
        }
    }

    assert_eq!(
        t.convex_hull(),
        vec![
            Point { x: 0.0, y: 0.0 },
            Point { x: 9.0, y: 0.0 },
            Point { x: 9.0, y: 9.0 },
            Point { x: 0.0, y: 9.0 }
        ]
    );
}

pub mod input_helper {
    //! A simple input helper for competitive programming.

    pub mod stdin_reader {
        use super::read::Read;
        use std::iter::FromIterator;

        /// Reads a single line from standard input with the specified type(s).
        ///
        /// # Examples
        /// ```no_run
        /// let (n, x, y): (usize, i64, i64) = read_line();
        /// let a: Vec<i64> = read_line();
        /// ```
        pub fn read_line<T: Read>() -> T {
            let mut buf = String::new();
            std::io::stdin().read_line(&mut buf).unwrap();
            Read::read(&mut buf.split_whitespace()).unwrap()
        }

        /// Reads multiple lines from standard input with the specified collection.
        ///
        /// # Example
        /// ```no_run
        /// let n: usize = read_line();
        /// let p: Vec<(i64, i64)> = read_multiple_lines(n);
        /// ```
        pub fn read_multiple_lines<T: Read, B: FromIterator<T>>(n: usize) -> B {
            (0..n).map(|_| read_line()).collect()
        }
    }

    mod read {
        use std::str::SplitWhitespace;

        pub trait Read: Sized {
            fn read(input: &mut SplitWhitespace) -> Option<Self>;
        }

        macro_rules! impl_read_for_types {
        ( $( $t : ty ), * ) => { $(
            impl Read for $t {
                fn read(input: &mut SplitWhitespace) -> Option<Self> {
                    match input.next() {
                        Some(v) => v.parse().ok(),
                        None => None,
                    }
                }
            }
        ) * };
    }

        impl_read_for_types!(i8, i16, i32, i64, i128, isize, u16, u32, u64, u128, usize, f32, f64);

        impl Read for String {
            fn read(input: &mut SplitWhitespace) -> Option<Self> {
                match input.next() {
                    Some(v) => Some(v.to_string()),
                    None => None,
                }
            }
        }

        /// Read String as Vec<u8>
        impl Read for Vec<u8> {
            fn read(input: &mut SplitWhitespace) -> Option<Self> {
                match input.next() {
                    Some(v) => Some(v.to_string().into_bytes()),
                    None => None,
                }
            }
        }

        /// Read String as Vec<char>
        impl Read for Vec<char> {
            fn read(input: &mut SplitWhitespace) -> Option<Self> {
                match input.next() {
                    Some(v) => Some(v.to_string().chars().collect()),
                    None => None,
                }
            }
        }

        macro_rules! impl_read_for_tuple {
        ( $( $t : ident ), * ) => {
            impl<$( $t : Read ), * > Read for ( $( $t ), * ) {
                fn read(input: &mut SplitWhitespace) -> Option<Self> {
                    Some( ( $( $t::read(input).unwrap() ), * ) )
                }
            }
        };
    }

        impl_read_for_tuple!(A, B);
        impl_read_for_tuple!(A, B, C);
        impl_read_for_tuple!(A, B, C, D);
        impl_read_for_tuple!(A, B, C, D, E);
        impl_read_for_tuple!(A, B, C, D, E, F);

        /// Read a whole line as Vec<T>
        impl<T: Read> Read for Vec<T> {
            fn read(input: &mut SplitWhitespace) -> Option<Self> {
                let mut vec = Vec::new();
                while let Some(v) = T::read(input) {
                    vec.push(v);
                }
                Some(vec)
            }
        }
    }
}