pub use input_helper::stdin_reader::*; fn main() { let mut v: Vec = 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>(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 { 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 = 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 = 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 = 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 = read_line(); /// ``` pub fn read_line() -> 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>(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; } macro_rules! impl_read_for_types { ( $( $t : ty ), * ) => { $( impl Read for $t { fn read(input: &mut SplitWhitespace) -> Option { 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 { match input.next() { Some(v) => Some(v.to_string()), None => None, } } } /// Read String as Vec impl Read for Vec { fn read(input: &mut SplitWhitespace) -> Option { match input.next() { Some(v) => Some(v.to_string().into_bytes()), None => None, } } } /// Read String as Vec impl Read for Vec { fn read(input: &mut SplitWhitespace) -> Option { 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 { 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 impl Read for Vec { fn read(input: &mut SplitWhitespace) -> Option { let mut vec = Vec::new(); while let Some(v) = T::read(input) { vec.push(v); } Some(vec) } } } }