結果

問題 No.1447 Greedy MtSaka
ユーザー cympfhcympfh
提出日時 2021-03-31 16:00:50
言語 Rust
(1.77.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 5,357 bytes
コンパイル時間 2,771 ms
コンパイル使用メモリ 157,708 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-21 14:03:54
合計ジャッジ時間 2,178 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 1 ms
4,376 KB
testcase_15 AC 1 ms
4,380 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 1 ms
4,380 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_imports, unused_macros, dead_code)]
use std::{cmp::*, collections::*};

fn main() {
    let mut sc = Scanner::new();
    let n: usize = sc.cin();
    let mut ps = vec![];
    for _ in 0..n {
        let x: f64 = sc.cin();
        let y: f64 = sc.cin();
        ps.push(Point(x, y));
    }
    let p = Polygon(ps);
    put!((p.area() * 2.0) as u64);
}

// @geometry2d/polygon
// @geometry2d/point
/// Geometry2D - Definition of Point
#[derive(Debug, Clone, Copy)]
pub struct Point(pub f64, pub f64);

impl Point {
    pub fn new(x: f64, y: f64) -> Self {
        Self(x, y)
    }
    pub fn zero() -> Point {
        Point(0.0, 0.0)
    }
    pub fn norm(&self) -> f64 {
        (*self * *self).sqrt()
    }
    pub fn det(&self, other: &Point) -> f64 {
        self.0 * other.1 - self.1 * other.0
    }
    pub fn arg(&self) -> f64 {
        let x = self.0 / self.norm();
        let y = self.1 / self.norm();
        y.atan2(x)
    }
    pub fn distance(&self, other: &Point) -> f64 {
        (*self - *other).norm()
    }
}
impl PartialEq for Point {
    fn eq(&self, other: &Point) -> bool {
        let eps = 1e-6;
        (self.0 - other.0).abs() < eps && (self.1 - other.1).abs() < eps
    }
    fn ne(&self, other: &Point) -> bool {
        !(self == other)
    }
}
impl Eq for Point {}
impl std::ops::Add for Point {
    type Output = Point;
    fn add(self, other: Point) -> Point {
        Point(self.0 + other.0, self.1 + other.1)
    }
}
impl std::ops::Neg for Point {
    type Output = Point;
    fn neg(self) -> Point {
        Point(-self.0, -self.1)
    }
}
impl std::ops::Sub for Point {
    type Output = Point;
    fn sub(self, other: Point) -> Point {
        self + (-other)
    }
}
// scalar multiplication
impl std::ops::Mul<Point> for f64 {
    type Output = Point;
    fn mul(self, other: Point) -> Point {
        Point(self * other.0, self * other.1)
    }
}
impl std::ops::Mul<f64> for Point {
    type Output = Point;
    fn mul(self, other: f64) -> Point {
        Point(other * self.0, other * self.1)
    }
}
// inner-product
impl std::ops::Mul<Point> for Point {
    type Output = f64;
    fn mul(self, other: Point) -> f64 {
        self.0 * other.0 + self.1 * other.1
    }
}
impl std::ops::Div<f64> for Point {
    type Output = Point;
    fn div(self, other: f64) -> Point {
        Point(self.0 / other, self.1 / other)
    }
}

/// Geometry2D - Definition of Polygon

#[derive(Debug, Clone)]
pub struct Polygon(Vec<Point>);

impl Polygon {
    pub fn len(&self) -> usize {
        self.0.len()
    }
}

impl std::ops::Index<usize> for Polygon {
    type Output = Point;
    fn index(&self, idx: usize) -> &Self::Output {
        &self.0[idx]
    }
}

impl Polygon {
    pub fn area(&self) -> f64 {
        (1..self.len() - 1)
            .map(|i| {
                let u = self[i] - self[0];
                let v = self[i + 1] - self[0];
                u.det(&v).abs()
            })
            .sum::<f64>()
            / 2.0
    }
}

#[macro_export]
macro_rules! poly {
    ($($x:expr),+) => {{
        let v = vec![$($x),+];
        Polygon(v)
    }};
    ($($x:expr),+ ,) => (poly!($($x),+))
}

// {{{
use std::io::{self, Write};
use std::str::FromStr;

struct Scanner {
    stdin: io::Stdin,
    buffer: VecDeque<String>,
}
impl Scanner {
    fn new() -> Self {
        Self {
            stdin: io::stdin(),
            buffer: VecDeque::new(),
        }
    }
    fn cin<T: FromStr>(&mut self) -> T {
        while self.buffer.is_empty() {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
        self.buffer.pop_front().unwrap().parse::<T>().ok().unwrap()
    }
    fn chars(&mut self) -> Vec<char> {
        self.cin::<String>().chars().collect()
    }
    fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.cin()).collect()
    }
}
fn flush() {
    std::io::stdout().flush().unwrap();
}
#[macro_export]
macro_rules! min {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        it.next().map(|z| it.fold(z, |x, y| min!(x, y)))
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = min!($($ys),*);
        if $x < t { $x } else { t }
    }}
}
#[macro_export]
macro_rules! max {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        it.next().map(|z| it.fold(z, |x, y| max!(x, y)))
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = max!($($ys),*);
        if $x > t { $x } else { t }
    }}
}
#[macro_export]
macro_rules! trace {
    ($x:expr) => {
        #[cfg(debug_assertions)]
        eprintln!(">>> {} = {:?}", stringify!($x), $x)
    };
    ($($xs:expr),*) => { trace!(($($xs),*)) }
}
#[macro_export]
macro_rules! put {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        if let Some(x) = it.next() { print!("{}", x); }
        for x in it { print!(" {}", x); }
        println!("");
    }};
    ($x:expr) => { println!("{}", $x) };
    ($x:expr, $($xs:expr),*) => { print!("{} ", $x); put!($($xs),*) }
}
#[macro_export]
macro_rules! ndarray {
    ($x:expr;) => {
        $x
    };
    ($x:expr; $size:expr $( , $rest:expr )*) => {
        vec![ndarray!($x; $($rest),*); $size]
    };
}

// }}}
0