#621948 (Rust) No.1041 直線大学

提出ソース

結果

問題	No.1041 直線大学
ユーザー	manta1130
提出日時	2021-02-24 22:03:57
言語	Rust (1.77.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	18,372 bytes
コンパイル時間	11,262 ms
コンパイル使用メモリ	377,392 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-04-28 00:18:27
合計ジャッジ時間	12,376 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	0 ms 5,376 KB
testcase_05	AC	1 ms 5,376 KB
testcase_06	AC	1 ms 5,376 KB
testcase_07	AC	1 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	1 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	1 ms 5,376 KB
testcase_14	AC	1 ms 5,376 KB
testcase_15	AC	1 ms 5,376 KB
testcase_16	AC	1 ms 5,376 KB
testcase_17	AC	0 ms 5,376 KB
testcase_18	AC	1 ms 5,376 KB
testcase_19	AC	1 ms 5,376 KB
testcase_20	AC	1 ms 5,376 KB
testcase_21	AC	1 ms 5,376 KB
testcase_22	AC	0 ms 5,376 KB
testcase_23	AC	1 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	1 ms 5,376 KB
testcase_26	AC	0 ms 5,376 KB
testcase_27	AC	1 ms 5,376 KB
testcase_28	AC	1 ms 5,376 KB
testcase_29	AC	1 ms 5,376 KB
testcase_30	AC	1 ms 5,376 KB
testcase_31	AC	1 ms 5,376 KB
testcase_32	AC	1 ms 5,376 KB
testcase_33	AC	0 ms 5,376 KB
testcase_34	AC	0 ms 5,376 KB
testcase_35	AC	0 ms 5,376 KB
testcase_36	AC	1 ms 5,376 KB
testcase_37	AC	0 ms 5,376 KB
testcase_38	AC	2 ms 5,376 KB
testcase_39	AC	1 ms 5,376 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

warning: unused attribute `macro_export`
   --> src/main.rs:535:5
    |
535 |     #[macro_export]
    |     ^^^^^^^^^^^^^^^
    |
note: the built-in attribute `macro_export` will be ignored, since it's applied to the macro invocation `thread_local`
   --> src/main.rs:536:5
    |
536 |     thread_local! {
    |     ^^^^^^^^^^^^
    = note: `#[warn(unused_attributes)]` on by default

warning: unused variable: `out`
 --> src/main.rs:6:13
  |
6 |     let mut out = BufWriter::new(out.lock());
  |             ^^^ help: if this is intentional, prefix it with an underscore: `_out`
  |
  = note: `#[warn(unused_variables)]` on by default

warning: variable does not need to be mutable
 --> src/main.rs:6:9
  |
6 |     let mut out = BufWriter::new(out.lock());
  |         ----^^^
  |         |
  |         help: remove this `mut`
  |
  = note: `#[warn(unused_mut)]` on by default

ソースコード

raw source code

#[allow(unused_imports)]
use std::io::{stdout, BufWriter, Write};

fn main() {
    let out = stdout();
    let mut out = BufWriter::new(out.lock());

    inputv! {
        n:usize,
    }
    let mut v = vec![];
    for _ in 0..n {
        inputv! {
            x:isize,y:isize,
        }
        v.push(Point::new(x, y));
    }
    let mut ans = 0;
    for i in 0..n {
        for j in i + 1..n {
            let mut count = 0;
            for k in 0..n {
                if is_parallel(v[i], v[k], v[j], v[k]) {
                    count += 1;
                }
            }
            ans = std::cmp::max(ans, count);
        }
    }
    println!("{}", ans);
}

//https://github.com/manta1130/competitive-template-rs

use geometry::*;
use input::*;

pub mod geometry {
    use std::collections::VecDeque;
    use std::default::Default;
    use std::ops::{Add, AddAssign, Div, Mul, Neg, Sub, SubAssign};

    #[derive(Debug, Copy, Clone, PartialEq)]
    pub struct Point<T> {
        pub x: T,
        pub y: T,
    }

    impl<T> Point<T> {
        pub fn new(x: T, y: T) -> Point<T> {
            Point { x, y }
        }
    }

    impl<T> Add for Point<T>
    where
        T: Add<Output = T>,
    {
        type Output = Point<T>;
        fn add(self, other: Point<T>) -> Point<T> {
            Point::new(self.x + other.x, self.y + other.y)
        }
    }

    impl<T> AddAssign for Point<T>
    where
        T: AddAssign,
    {
        fn add_assign(&mut self, other: Point<T>) {
            self.x += other.x;
            self.y += other.y;
        }
    }

    impl<T> Sub for Point<T>
    where
        T: Sub<Output = T>,
    {
        type Output = Point<T>;
        fn sub(self, other: Point<T>) -> Point<T> {
            Point::new(self.x - other.x, self.y - other.y)
        }
    }

    impl<T> SubAssign for Point<T>
    where
        T: SubAssign,
    {
        fn sub_assign(&mut self, other: Point<T>) {
            self.x -= other.x;
            self.y -= other.y;
        }
    }

    #[derive(Debug, Copy, Clone, PartialEq, Eq)]
    pub enum LineStatus {
        Horizontal,
        Vertical,
        Normal,
    }

    #[derive(Debug, Copy, Clone, PartialEq)]
    pub struct Line<T> {
        a: T,
        b: T,
        status: LineStatus,
    }

    impl<T> Line<T>
    where
        T: Copy
            + Clone
            + Add<Output = T>
            + Sub<Output = T>
            + Div<Output = T>
            + Mul<Output = T>
            + PartialEq
            + Neg
            + Default,
    {
        pub fn new(a: T, b: T) -> Line<T> {
            Line {
                a,
                b,
                status: LineStatus::Normal,
            }
        }

        #[allow(clippy::eq_op)]
        pub fn new_horizontal(y: T) -> Line<T> {
            Line {
                a: T::default(),
                b: y,
                status: LineStatus::Horizontal,
            }
        }

        #[allow(clippy::eq_op)]
        pub fn new_vertical(x: T) -> Line<T> {
            Line {
                a: T::default(),
                b: x,
                status: LineStatus::Vertical,
            }
        }

        pub fn from(l1: Point<T>, l2: Point<T>) -> Option<Line<T>> {
            if l1 == l2 {
                return None;
            }

            let (a, b, status);
            if l1.x == l2.x {
                a = T::default();
                b = l1.x;
                status = LineStatus::Vertical;
            } else if l1.y == l2.y {
                a = T::default();
                b = l1.y;
                status = LineStatus::Horizontal;
            } else {
                a = (l1.y - l2.y) / (l1.x - l2.x);
                b = l1.y - a * l1.x;
                status = LineStatus::Normal;
            }
            Some(Line { a, b, status })
        }

        pub fn from_point_slope(p: Point<T>, a: T, s: LineStatus) -> Line<T> {
            if s == LineStatus::Horizontal {
                Line::new_horizontal(p.y)
            } else if s == LineStatus::Vertical {
                Line::new_vertical(p.x)
            } else {
                Line::new(a, p.y - a * p.x)
            }
        }

        pub fn get_intersection(&self, other: Line<T>) -> Option<Point<T>> {
            if self.get_status() == LineStatus::Normal && other.get_status() == LineStatus::Normal {
                let x = (other.get_intercept() - self.get_intercept())
                    / (self.get_slope() - other.get_slope());
                Some(Point {
                    x,
                    y: x * self.get_slope() + self.get_intercept(),
                })
            } else if self.status == other.status {
                None
            } else if self.is_horizontal() && other.is_vertical() {
                Some(Point {
                    x: other.get_intercept(),
                    y: self.get_intercept(),
                })
            } else if self.is_vertical() && other.is_horizontal() {
                Some(Point {
                    y: other.get_intercept(),
                    x: self.get_intercept(),
                })
            } else if self.is_horizontal() || self.is_vertical() {
                if self.is_horizontal() {
                    let y = self.get_intercept();
                    Some(Point {
                        x: other.substitution_y(y).unwrap(),
                        y,
                    })
                } else {
                    let x = self.get_intercept();
                    Some(Point {
                        x,
                        y: other.substitution_x(x).unwrap(),
                    })
                }
            } else if other.is_horizontal() {
                let y = other.get_intercept();
                Some(Point {
                    x: self.substitution_y(y).unwrap(),
                    y,
                })
            } else {
                let x = other.get_intercept();
                Some(Point {
                    x,
                    y: self.substitution_x(x).unwrap(),
                })
            }
        }

        pub fn get_slope(&self) -> T {
            self.a
        }

        pub fn get_intercept(&self) -> T {
            self.b
        }

        pub fn get_data(&self) -> (T, T) {
            (self.a, self.b)
        }

        pub fn is_horizontal(&self) -> bool {
            self.status == LineStatus::Horizontal
        }

        pub fn is_vertical(&self) -> bool {
            self.status == LineStatus::Vertical
        }

        pub fn get_status(&self) -> LineStatus {
            self.status
        }

        pub fn substitution_x(&self, x: T) -> Option<T> {
            if self.is_horizontal() {
                Some(self.get_intercept())
            } else if self.is_vertical() {
                None
            } else {
                Some(self.get_slope() * x + self.get_intercept())
            }
        }

        pub fn substitution_y(&self, y: T) -> Option<T> {
            if self.is_horizontal() {
                None
            } else if self.is_vertical() {
                Some(self.get_intercept())
            } else {
                Some((y - self.get_intercept()) / self.get_slope())
            }
        }
    }

    impl<T> Line<T>
    where
        T: Copy
            + Clone
            + Add<Output = T>
            + Sub<Output = T>
            + Div<Output = T>
            + Mul<Output = T>
            + PartialEq
            + Neg
            + Default
            + Into<f64>,
    {
        pub fn get_perpendicular(&self, p: Point<T>) -> Line<f64> {
            Line::from_point_slope(
                Point::new(p.x.into(), p.y.into()),
                -(1.0 / self.get_slope().into()),
                match self.get_status() {
                    LineStatus::Horizontal => LineStatus::Vertical,
                    LineStatus::Vertical => LineStatus::Horizontal,
                    LineStatus::Normal => LineStatus::Normal,
                },
            )
        }
    }

    pub fn cross<T>(p1: Point<T>, p2: Point<T>) -> T
    where
        T: Sub<Output = T> + Mul<Output = T>,
    {
        p1.x * p2.y - p1.y * p2.x
    }

    pub fn dot<T>(p1: Point<T>, p2: Point<T>) -> T
    where
        T: Add<Output = T> + Mul<Output = T>,
    {
        p1.x * p2.x + p1.y * p2.y
    }

    pub fn norm<T>(p: Point<T>) -> T
    where
        T: Mul<Output = T> + Add<Output = T> + Copy,
    {
        p.x * p.x + p.y * p.y
    }

    pub fn ccw<T>(a: Point<T>, mut b: Point<T>, mut c: Point<T>) -> isize
    where
        T: SubAssign
            + Sub<Output = T>
            + Mul<Output = T>
            + Copy
            + PartialOrd
            + Add<Output = T>
            + Default,
    {
        let zero = T::default();
        b -= a;
        c -= a;
        if cross(b, c) > zero {
            1
        } else if cross(b, c) < zero {
            -1
        } else if dot(b, c) < zero {
            2
        } else if norm(b) < norm(c) {
            -2
        } else {
            0
        }
    }

    pub fn is_parallel<T>(p11: Point<T>, p12: Point<T>, p21: Point<T>, p22: Point<T>) -> bool
    where
        T: Sub<Output = T> + Mul<Output = T> + PartialEq,
    {
        (p12.y - p11.y) * (p22.x - p21.x) == (p22.y - p21.y) * (p12.x - p11.x)
    }

    pub fn is_orthogonal<T>(p11: Point<T>, p12: Point<T>, p21: Point<T>, p22: Point<T>) -> bool
    where
        T: Sub<Output = T> + Mul<Output = T> + Neg<Output = T> + PartialEq,
    {
        (p12.y - p11.y) * (p22.y - p21.y) == -(p22.x - p21.x) * (p12.x - p11.x)
    }

    pub fn arg_sort<T>(v: &mut [Point<T>], origin: Point<T>, start: Point<T>)
    where
        T: Add<Output = T>
            + Sub<Output = T>
            + SubAssign
            + Mul<Output = T>
            + PartialOrd
            + Copy
            + Default,
    {
        arg_sort_internal(v, origin, start, 0, v.len(), true);
    }

    #[allow(clippy::many_single_char_names)]
    fn arg_sort_internal<T>(
        v: &mut [Point<T>],
        origin: Point<T>,
        pivot: Point<T>,
        f: usize,
        t: usize,
        flag: bool,
    ) where
        T: Add<Output = T>
            + Sub<Output = T>
            + SubAssign
            + Mul<Output = T>
            + PartialOrd
            + Copy
            + Default,
    {
        if f == t {
            return;
        }
        let zero = T::default();

        let mut plus = vec![];
        let mut minus = vec![];
        let mut inv = vec![];
        let mut r = vec![];
        let mut origin_count = 0_usize;

        for &it in v.iter().take(t).skip(f) {
            let p = pivot - origin;
            let c = it - origin;
            let cx = cross(p, c);
            if it == origin {
                origin_count += 1;
            } else if zero < cx {
                plus.push(it);
            } else if zero > cx {
                minus.push(it);
            } else if dot(pivot - origin, it - origin) < zero {
                inv.push(it);
            } else {
                r.push(it);
            }
        }

        for _ in 0..origin_count {
            r.insert(0, origin);
        }

        let mut po = f;
        if flag {
            for &i in &r {
                v[po] = i;
                po += 1;
            }
            for &i in &plus {
                v[po] = i;
                po += 1;
            }
            for &i in &inv {
                v[po] = i;
                po += 1;
            }
            for &i in &minus {
                v[po] = i;
                po += 1;
            }
            let ps = f + r.len();
            let pe = f + r.len() + plus.len();
            let ms = f + r.len() + plus.len() + inv.len();
            let me = f + r.len() + plus.len() + inv.len() + minus.len();
            if ps != pe {
                arg_sort_internal(v, origin, v[ps], ps, pe, false);
            }
            if ms != me {
                arg_sort_internal(v, origin, v[ms], ms, me, false);
            }
        } else {
            for &i in &minus {
                v[po] = i;
                po += 1;
            }
            for &i in &r {
                v[po] = i;
                po += 1;
            }
            for &i in &plus {
                v[po] = i;
                po += 1;
            }
            for &i in &inv {
                v[po] = i;
                po += 1;
            }
            let ms = f;
            let me = f + minus.len();
            let ps = f + minus.len() + r.len();
            let pe = f + minus.len() + r.len() + plus.len();

            if ps != pe {
                arg_sort_internal(v, origin, v[ps], ps, pe, false);
            }
            if ms != me {
                arg_sort_internal(v, origin, v[ms], ms, me, false);
            }
        }
    }

    pub fn graham_scan<T>(list: &mut [Point<T>]) -> Vec<Point<T>>
    where
        T: Add<Output = T>
            + Sub<Output = T>
            + SubAssign
            + Mul<Output = T>
            + Ord
            + Copy
            + Default
            + From<i8>
            + std::fmt::Debug,
    {
        if list.len() <= 2 {
            return Vec::new();
        }
        list.sort_by_key(|p| (p.y, p.x));
        let pivot = Point::new(list[0].x + 1_i8.into(), list[0].y);
        arg_sort(list, list[0], pivot);

        let mut list_dedup = vec![list[0], list[1]];
        let origin = list_dedup[0];
        for &p in list.iter().skip(2) {
            let top = *list_dedup.last().unwrap();
            if cross(top - origin, p - origin) != T::default() {
                list_dedup.push(p);
            } else if norm(top - origin) < norm(p - origin) {
                list_dedup.pop();
                list_dedup.push(p);
            }
        }

        let list = list_dedup;
        let mut stack = VecDeque::new();

        stack.push_front(list[0]);
        stack.push_front(list[1]);
        stack.push_front(list[2]);

        for &p in list.iter().skip(3) {
            while ccw(stack[1], stack[0], p) != 1 {
                stack.pop_front();
            }
            stack.push_front(p);
        }

        stack.iter().rev().cloned().collect::<Vec<_>>()
    }
}
pub mod input {
    use std::cell::RefCell;
    use std::io;
    pub const SPLIT_DELIMITER: char = ' ';
    pub use std::io::prelude::*;

    #[macro_export]
    thread_local! {
        pub static INPUT_BUFFER:RefCell<std::collections::VecDeque<String>>=RefCell::new(std::collections::VecDeque::new());
    }

    #[macro_export]
    macro_rules! input_internal {
        ($x:ident : $t:ty) => {
            INPUT_BUFFER.with(|p| {
                if p.borrow().len() == 0 {
                    let temp_str = input_line_str();
                    let mut split_result_iter = temp_str
                        .split(SPLIT_DELIMITER)
                        .map(|q| q.to_string())
                        .collect::<std::collections::VecDeque<_>>();
                    p.borrow_mut().append(&mut split_result_iter)
                }
            });
            let mut buf_split_result = String::new();
            INPUT_BUFFER.with(|p| buf_split_result = p.borrow_mut().pop_front().unwrap());
            let $x: $t = buf_split_result.parse().unwrap();
        };
        (mut $x:ident : $t:ty) => {
            INPUT_BUFFER.with(|p| {
                if p.borrow().len() == 0 {
                    let temp_str = input_line_str();
                    let mut split_result_iter = temp_str
                        .split(SPLIT_DELIMITER)
                        .map(|q| q.to_string())
                        .collect::<std::collections::VecDeque<_>>();
                    p.borrow_mut().append(&mut split_result_iter)
                }
            });
            let mut buf_split_result = String::new();
            INPUT_BUFFER.with(|p| buf_split_result = p.borrow_mut().pop_front().unwrap());
            let mut $x: $t = buf_split_result.parse().unwrap();
        };
    }

    #[macro_export]
    macro_rules! inputv {
    ($i:ident : $t:ty) => {
        input_internal!{$i : $t}
    };
    (mut $i:ident : $t:ty) => {
        input_internal!{mut $i : $t}
    };
    ($i:ident : $t:ty $(,)*) => {
            input_internal!{$i : $t}
    };
    (mut $i:ident : $t:ty $(,)*) => {
            input_internal!{mut $i : $t}
    };
    (mut $i:ident : $t:ty,$($q:tt)*) => {
            input_internal!{mut $i : $t}
            inputv!{$($q)*}
    };
    ($i:ident : $t:ty,$($q:tt)*) => {
            input_internal!{$i : $t}
            inputv!{$($q)*}
    };
}

    pub fn input_all() {
        INPUT_BUFFER.with(|p| {
            if p.borrow().len() == 0 {
                let mut temp_str = String::new();
                std::io::stdin().read_to_string(&mut temp_str).unwrap();
                let mut split_result_iter = temp_str
                    .split_whitespace()
                    .map(|q| q.to_string())
                    .collect::<std::collections::VecDeque<_>>();
                p.borrow_mut().append(&mut split_result_iter)
            }
        });
    }

    pub fn input_line_str() -> String {
        let mut s = String::new();
        io::stdin().read_line(&mut s).unwrap();
        s.trim().to_string()
    }

    #[allow(clippy::match_wild_err_arm)]
    pub fn input_vector<T>() -> Vec<T>
    where
        T: std::str::FromStr,
    {
        let mut v: Vec<T> = Vec::new();

        let s = input_line_str();
        let split_result = s.split(SPLIT_DELIMITER);
        for z in split_result {
            let buf = match z.parse() {
                Ok(r) => r,
                Err(_) => panic!("Parse Error",),
            };
            v.push(buf);
        }
        v
    }

    #[allow(clippy::match_wild_err_arm)]
    pub fn input_vector_row<T>(n: usize) -> Vec<T>
    where
        T: std::str::FromStr,
    {
        let mut v = Vec::with_capacity(n);
        for _ in 0..n {
            let buf = match input_line_str().parse() {
                Ok(r) => r,
                Err(_) => panic!("Parse Error",),
            };
            v.push(buf);
        }
        v
    }

    pub trait ToCharVec {
        fn to_charvec(&self) -> Vec<char>;
    }

    impl ToCharVec for String {
        fn to_charvec(&self) -> Vec<char> {
            self.to_string().chars().collect::<Vec<_>>()
        }
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード