提出 #16525659

---

ソースコード 拡げる

// template {{{
#![allow(clippy::many_single_char_names)]

#[allow(dead_code)]
mod ngtio {
    use ::std::collections::VecDeque;

    pub struct Buffer {
        buf: VecDeque<String>,
    }

    impl Buffer {
        pub fn new() -> Self {
            Self {
                buf: VecDeque::new(),
            }
        }

        fn load(&mut self) {
            while self.buf.is_empty() {
                let mut s = String::new();
                let length = ::std::io::stdin().read_line(&mut s).unwrap();
                if length == 0 {
                    break;
                }
                self.buf.extend(s.split_whitespace().map(|s| s.to_owned()));
            }
        }

        pub fn string(&mut self) -> String {
            self.load();
            self.buf
                .pop_front()
                .unwrap_or_else(|| panic!("入力が終了したのですが。"))
        }

        pub fn string_char_vec(&mut self) -> Vec<char> {
            let s = self.string();
            s.chars().collect::<Vec<_>>()
        }

        pub fn string_char_vec_trusted_len(&mut self, len: usize) -> Vec<char> {
            let s = self.string();
            let s = s.chars().collect::<Vec<_>>();
            assert_eq!(s.len(), len, "あら、思ったのと長さ違いますね……");
            s
        }

        pub fn char(&mut self) -> char {
            let string = self.string();
            let mut chars = string.chars();
            let res = chars.next().unwrap();
            assert!(
                chars.next().is_none(),
                "char で受け取りたいのも山々なのですが、さては 2 文字以上ありますね？"
            );
            res
        }

        pub fn read<T: ::std::str::FromStr>(&mut self) -> T
        where
            <T as ::std::str::FromStr>::Err: ::std::fmt::Debug,
        {
            self.string()
                .parse::<T>()
                .expect("Failed to parse the input.")
        }

        pub fn read_vec<T: ::std::str::FromStr>(&mut self, len: usize) -> Vec<T>
        where
            <T as ::std::str::FromStr>::Err: ::std::fmt::Debug,
        {
            (0..len).map(|_| self.read::<T>()).collect()
        }
    }

    macro_rules! define_primitive_reader {
        ($($ty:tt,)*) => {
            impl Buffer {
                $(
#[inline]
                    pub fn $ty(&mut self) -> $ty {
                        self.read::<$ty>()
                    }
                )*
            }
        }
    }

    define_primitive_reader! {
        u8, u16, u32, u64, usize,
        i8, i16, i32, i64, isize,
    }

    impl Default for Buffer {
        fn default() -> Self {
            Self::new()
        }
    }
}

#[allow(unused_imports)]
use std::{collections, iter, mem, ops};
// }}}
// seq {{{
#[allow(dead_code)]
mod seq {
    #![warn(missing_docs, missing_doc_code_examples)]

    pub use self::accumulate::{accumulate, Accumulate};
    pub use self::adjacent::{adjacent, Adjacent};
    pub use self::aoj_copied::AojCopied;
    pub use self::cartesian_product::{cartesian_product, CartesianProduct};
    pub use self::format_intersparse::format_intersparse;
    pub use self::grid_next::{grid_next, GridNext};
    pub use self::intersperse::{intersperse, Intersperse};
    pub use self::mul_step::{mul_step, MulStep};
    pub use self::repeat_with::{repeat_with, RepeatWith};
    pub use self::step::{step, Step};

    use std::{fmt, ops};

    impl<I: Iterator> Seq for I {}

    pub trait Seq: Iterator + Sized {
        fn adjacent(self) -> Adjacent<Self, Self::Item>
        where
            Self::Item: Clone,
        {
            adjacent(self)
        }

        fn grid_next(self, ij: (usize, usize), h: usize, w: usize) -> GridNext<Self>
        where
            Self: Iterator<Item = (i64, i64)>,
        {
            grid_next(self, ij, h, w)
        }

        fn aoj_copied<'a, T: 'a>(self) -> AojCopied<Self>
        where
            Self: Sized + Iterator<Item = &'a T>,
            T: Copy,
        {
            AojCopied { iter: self }
        }

        fn cartesian_product<J>(self, other: J) -> CartesianProduct<Self, J::IntoIter>
        where
            Self: Sized,
            Self::Item: Clone,
            J: IntoIterator,
            J::IntoIter: Clone,
        {
            cartesian_product::cartesian_product(self, other.into_iter())
        }

        fn accumulate<T>(self, init: T) -> Accumulate<Self, T>
        where
            T: Clone + ops::AddAssign<Self::Item>,
        {
            accumulate::accumulate(self, init)
        }

        fn intersperse(self, elt: Self::Item) -> Intersperse<Self> {
            intersperse::intersperse(self, elt)
        }

        fn format_intersparse<T>(self, separator: T) -> String
        where
            Self::Item: fmt::Display,
            T: fmt::Display,
        {
            self.map(|x| format!("{}", x))
                .intersperse(format!("{}", separator))
                .collect::<String>()
        }
    }

    mod aoj_copied {
        use std::iter::DoubleEndedIterator;

        #[allow(missing_docs)]
        #[derive(Debug, Clone)]
        pub struct AojCopied<I> {
            pub iter: I,
        }

        impl<'a, I, T: 'a> Iterator for AojCopied<I>
        where
            I: Iterator<Item = &'a T>,
            T: Copy,
        {
            type Item = T;

            fn next(&mut self) -> Option<T> {
                self.iter.next().map(|&x| x)
            }

            fn size_hint(&self) -> (usize, Option<usize>) {
                self.iter.size_hint()
            }

            fn fold<Acc, F>(self, initer: Acc, mut f: F) -> Acc
            where
                F: FnMut(Acc, Self::Item) -> Acc,
            {
                self.iter.fold(initer, move |acc, &elt| f(acc, elt))
            }

            fn nth(&mut self, n: usize) -> Option<T> {
                self.iter.nth(n).map(|&x| x)
            }

            fn last(self) -> Option<T> {
                self.iter.last().map(|&x| x)
            }

            fn count(self) -> usize {
                self.iter.count()
            }
        }

        impl<'a, I, T: 'a> DoubleEndedIterator for AojCopied<I>
        where
            I: DoubleEndedIterator<Item = &'a T>,
            T: Copy,
        {
            fn next_back(&mut self) -> Option<T> {
                self.iter.next_back().map(|&x| x)
            }
        }

        impl<'a, I, T: 'a> ExactSizeIterator for AojCopied<I>
        where
            I: ExactSizeIterator<Item = &'a T>,
            T: Copy,
        {
            fn len(&self) -> usize {
                self.iter.len()
            }
        }
    }

    mod adjacent {
        #[allow(missing_docs)]
        pub fn adjacent<I, T>(mut iter: I) -> Adjacent<I, T>
        where
            I: Iterator<Item = T>,
            T: Clone,
        {
            if let Some(first) = iter.next() {
                Adjacent {
                    iter,
                    prv: Some(first),
                }
            } else {
                Adjacent { iter, prv: None }
            }
        }

        #[allow(missing_docs)]
        pub struct Adjacent<I, T>
        where
            I: Iterator<Item = T>,
        {
            iter: I,
            prv: Option<T>,
        }

        impl<I, T> Iterator for Adjacent<I, T>
        where
            I: Iterator<Item = T>,
            T: Clone,
        {
            type Item = (T, T);

            fn next(&mut self) -> Option<(T, T)> {
                self.prv.as_ref().cloned().and_then(|first| {
                    self.iter.next().map(|second| {
                        self.prv = Some(second.clone());
                        (first, second)
                    })
                })
            }
        }
    }

    mod grid_next {
        #[allow(missing_docs)]
        pub fn grid_next<T>(difference: T, ij: (usize, usize), h: usize, w: usize) -> GridNext<T>
        where
            T: Iterator<Item = (i64, i64)>,
        {
            GridNext {
                i: ij.0 as i64,
                j: ij.1 as i64,
                h: h as i64,
                w: w as i64,
                difference,
            }
        }

        #[allow(missing_docs)]
        #[derive(Debug, Clone)]
        pub struct GridNext<T> {
            i: i64,
            j: i64,
            h: i64,
            w: i64,
            difference: T,
        }

        impl<T> Iterator for GridNext<T>
        where
            T: Iterator<Item = (i64, i64)>,
        {
            type Item = (usize, usize);

            fn next(&mut self) -> Option<(usize, usize)> {
                while let Some((di, dj)) = self.difference.next() {
                    let ni = self.i + di;
                    let nj = self.j + dj;
                    if 0 <= ni && ni < self.h && 0 <= nj && nj < self.w {
                        return Some((ni as usize, nj as usize));
                    }
                }
                None
            }
        }
    }

    mod step {
        #[allow(missing_docs)]
        pub fn step<T, U>(init: T, step: U) -> Step<T, U>
        where
            T: Copy,
            U: Copy,
            T: ::std::ops::Add<U, Output = T>,
        {
            Step { now: init, step }
        }

        #[allow(missing_docs)]
        #[derive(Debug, Clone)]
        pub struct Step<T, U> {
            now: T,
            step: U,
        }

        #[allow(missing_docs)]
        impl<T, U> Iterator for Step<T, U>
        where
            T: Copy,
            U: Copy,
            T: ::std::ops::Add<U, Output = T>,
        {
            type Item = T;

            fn next(&mut self) -> Option<T> {
                let next = self.now + self.step;
                Some(::std::mem::replace(&mut self.now, next))
            }
        }
    }

    mod mul_step {
        #[allow(missing_docs)]
        pub fn mul_step<T, U>(init: T, step: U) -> MulStep<T, U>
        where
            T: Copy,
            U: Copy,
            T: ::std::ops::Mul<U, Output = T>,
        {
            MulStep { now: init, step }
        }

        #[allow(missing_docs)]
        #[derive(Debug, Clone)]
        pub struct MulStep<T, U> {
            now: T,
            step: U,
        }

        #[allow(missing_docs)]
        impl<T, U> Iterator for MulStep<T, U>
        where
            T: Copy,
            U: Copy,
            T: ::std::ops::Mul<U, Output = T>,
        {
            type Item = T;

            fn next(&mut self) -> Option<T> {
                let next = self.now * self.step;
                Some(::std::mem::replace(&mut self.now, next))
            }
        }
    }

    mod repeat_with {
        #[allow(missing_docs)]
        pub fn repeat_with<A, F: FnMut() -> A>(repeater: F) -> RepeatWith<F> {
            RepeatWith { repeater }
        }

        #[allow(missing_docs)]
        #[derive(Debug, Clone)]
        pub struct RepeatWith<F> {
            repeater: F,
        }

        impl<A, F: FnMut() -> A> Iterator for RepeatWith<F> {
            type Item = A;

            #[inline]
            fn next(&mut self) -> Option<A> {
                Some((self.repeater)())
            }

            #[inline]
            fn size_hint(&self) -> (usize, Option<usize>) {
                (::std::usize::MAX, None)
            }
        }
    }

    mod accumulate {
        use super::*;

        #[allow(missing_docs)]
        #[derive(Debug, Clone)]
        pub struct Accumulate<I, T> {
            prev: Option<T>,
            iter: I,
        }

        #[allow(missing_docs)]
        pub fn accumulate<I, T>(iter: I, init: T) -> Accumulate<I, T>
        where
            I: Iterator,
            T: Clone + ops::AddAssign<I::Item>,
        {
            Accumulate {
                prev: Some(init),
                iter,
            }
        }

        impl<I, T> Iterator for Accumulate<I, T>
        where
            I: Iterator,
            T: Clone + ops::AddAssign<I::Item>,
        {
            type Item = T;

            fn next(&mut self) -> Option<T> {
                let res = self.prev.clone();
                if let Some(prev) = self.prev.as_mut() {
                    if let Some(next) = self.iter.next() {
                        *prev += next;
                    } else {
                        self.prev = None;
                    }
                }
                res
            }

            fn size_hint(&self) -> (usize, Option<usize>) {
                size_hint::add_scalar(self.iter.size_hint(), 1)
            }
        }
    }

    mod cartesian_product {
        #[allow(missing_docs)]
        #[derive(Debug, Clone)]
        pub struct CartesianProduct<I, J>
        where
            I: Iterator,
        {
            a: I,
            a_cur: Option<I::Item>,
            b: J,
            b_orig: J,
        }

        #[allow(missing_docs)]
        pub fn cartesian_product<I, J>(mut i: I, j: J) -> CartesianProduct<I, J>
        where
            I: Iterator,
            J: Clone + Iterator,
            I::Item: Clone,
        {
            CartesianProduct {
                a_cur: i.next(),
                a: i,
                b_orig: j.clone(),
                b: j,
            }
        }

        impl<I, J> Iterator for CartesianProduct<I, J>
        where
            I: Iterator,
            J: Clone + Iterator,
            I::Item: Clone,
        {
            type Item = (I::Item, J::Item);

            fn next(&mut self) -> Option<(I::Item, J::Item)> {
                let elt_b = match self.b.next() {
                    None => {
                        self.b = self.b_orig.clone();
                        match self.b.next() {
                            None => return None,
                            Some(x) => {
                                self.a_cur = self.a.next();
                                x
                            }
                        }
                    }
                    Some(x) => x,
                };
                match self.a_cur {
                    None => None,
                    Some(ref a) => Some((a.clone(), elt_b)),
                }
            }

            fn size_hint(&self) -> (usize, Option<usize>) {
                let has_cur = self.a_cur.is_some() as usize;
                // Not ExactSizeIterator because size may be larger than usize
                let (b_min, b_max) = self.b.size_hint();

                // Compute a * b_orig + b for both lower and upper bound
                super::size_hint::add(
                    super::size_hint::mul(self.a.size_hint(), self.b_orig.size_hint()),
                    (b_min * has_cur, b_max.map(move |x| x * has_cur)),
                )
            }

            fn fold<Acc, G>(mut self, mut accum: Acc, mut f: G) -> Acc
            where
                G: FnMut(Acc, Self::Item) -> Acc,
            {
                if let Some(mut a) = self.a_cur.take() {
                    let mut b = self.b;
                    loop {
                        accum = b.fold(accum, |acc, elt| f(acc, (a.clone(), elt)));

                        // we can only continue iterating a if we had a first element;
                        if let Some(next_a) = self.a.next() {
                            b = self.b_orig.clone();
                            a = next_a;
                        } else {
                            break;
                        }
                    }
                }
                accum
            }
        }
    }

    #[allow(missing_docs)]
    mod intersperse {
        use super::size_hint;
        use std::iter;

        #[derive(Debug, Clone)]
        #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
        pub struct Intersperse<I>
        where
            I: Iterator,
        {
            element: I::Item,
            iter: iter::Fuse<I>,
            peek: Option<I::Item>,
        }

        pub fn intersperse<I>(iter: I, elt: I::Item) -> Intersperse<I>
        where
            I: Iterator,
        {
            let mut iter = iter.fuse();
            Intersperse {
                peek: iter.next(),
                iter,
                element: elt,
            }
        }

        impl<I> Iterator for Intersperse<I>
        where
            I: Iterator,
            I::Item: Clone,
        {
            type Item = I::Item;
            #[inline]
            fn next(&mut self) -> Option<I::Item> {
                if self.peek.is_some() {
                    self.peek.take()
                } else {
                    self.peek = self.iter.next();
                    if self.peek.is_some() {
                        Some(self.element.clone())
                    } else {
                        None
                    }
                }
            }

            fn size_hint(&self) -> (usize, Option<usize>) {
                // 2 * SH + { 1 or 0 }
                let has_peek = self.peek.is_some() as usize;
                let sh = self.iter.size_hint();
                size_hint::add_scalar(size_hint::add(sh, sh), has_peek)
            }

            fn fold<B, F>(mut self, init: B, mut f: F) -> B
            where
                Self: Sized,
                F: FnMut(B, Self::Item) -> B,
            {
                let mut accum = init;

                if let Some(x) = self.peek.take() {
                    accum = f(accum, x);
                }

                let element = &self.element;

                self.iter.fold(accum, |accum, x| {
                    let accum = f(accum, element.clone());
                    f(accum, x)
                })
            }
        }
    }

    #[allow(missing_docs)]
    mod format_intersparse {
        use super::Seq;
        use std::fmt;

        pub fn format_intersparse<I, T>(iter: I, separator: T) -> String
        where
            I: Iterator,
            I::Item: fmt::Display,
            T: fmt::Display,
        {
            iter.map(|x| format!("{}", x))
                .intersperse(format!("{}", separator))
                .collect::<String>()
        }
    }

    mod size_hint {

        use std::cmp;
        use std::usize;

        pub type SizeHint = (usize, Option<usize>);

        #[inline]
        pub fn add(a: SizeHint, b: SizeHint) -> SizeHint {
            let min = a.0.saturating_add(b.0);
            let max = match (a.1, b.1) {
                (Some(x), Some(y)) => x.checked_add(y),
                _ => None,
            };

            (min, max)
        }

        #[inline]
        #[allow(dead_code)]
        pub fn add_scalar(sh: SizeHint, x: usize) -> SizeHint {
            let (mut low, mut hi) = sh;
            low = low.saturating_add(x);
            hi = hi.and_then(|elt| elt.checked_add(x));
            (low, hi)
        }

        #[inline]
        #[allow(dead_code)]
        pub fn sub_scalar(sh: SizeHint, x: usize) -> SizeHint {
            let (mut low, mut hi) = sh;
            low = low.saturating_sub(x);
            hi = hi.map(|elt| elt.saturating_sub(x));
            (low, hi)
        }

        #[inline]
        #[allow(dead_code)]
        pub fn mul(a: SizeHint, b: SizeHint) -> SizeHint {
            let low = a.0.saturating_mul(b.0);
            let hi = match (a.1, b.1) {
                (Some(x), Some(y)) => x.checked_mul(y),
                (Some(0), None) | (None, Some(0)) => Some(0),
                _ => None,
            };
            (low, hi)
        }

        #[inline]
        #[allow(dead_code)]
        pub fn mul_scalar(sh: SizeHint, x: usize) -> SizeHint {
            let (mut low, mut hi) = sh;
            low = low.saturating_mul(x);
            hi = hi.and_then(|elt| elt.checked_mul(x));
            (low, hi)
        }

        #[inline]
        #[allow(dead_code)]
        pub fn max(a: SizeHint, b: SizeHint) -> SizeHint {
            let (a_lower, a_upper) = a;
            let (b_lower, b_upper) = b;

            let lower = cmp::max(a_lower, b_lower);

            let upper = match (a_upper, b_upper) {
                (Some(x), Some(y)) => Some(cmp::max(x, y)),
                _ => None,
            };

            (lower, upper)
        }

        #[inline]
        #[allow(dead_code)]
        pub fn min(a: SizeHint, b: SizeHint) -> SizeHint {
            let (a_lower, a_upper) = a;
            let (b_lower, b_upper) = b;
            let lower = cmp::min(a_lower, b_lower);
            let upper = match (a_upper, b_upper) {
                (Some(u1), Some(u2)) => Some(cmp::min(u1, u2)),
                _ => a_upper.or(b_upper),
            };
            (lower, upper)
        }
    }
}
// }}}
// dbg {{{
#[allow(dead_code)]
mod dbg {
    #[macro_export]
    macro_rules! lg {
        () => {
            $crate::eprintln!("[{}:{}]", $crate::file!(), $crate::line!());
        };
        ($val:expr) => {
            match $val {
                tmp => {
                    eprintln!("[{}:{}] {} = {:?}",
                        file!(), line!(), stringify!($val), &tmp);
                    tmp
                }
            }
        };
        ($val:expr,) => { lg!($val) };
        ($($val:expr),+ $(,)?) => {
            ($(lg!($val)),+,)
        };
    }

    #[macro_export]
    macro_rules! lg_nl {
        () => {
            $crate::eprintln!("[{}:{}]", $crate::file!(), $crate::line!());
        };
        ($val:expr) => {
            match $val {
                tmp => {
                    eprintln!("[{}:{}] {}:\n{:?}", file!(), line!(), stringify!($val), tmp);
                    tmp
                }
            };
        };
    }

    #[macro_export]
    macro_rules! msg {
        () => {
            compile_error!();
        };
        ($msg:expr) => {
            $crate::eprintln!("[{}:{}][{}]", $crate::file!(), $crate::line!(), $msg);
        };
        ($msg:expr, $val:expr) => {
            match $val {
                tmp => {
                    eprintln!("[{}:{}][{}] {} = {:?}",
                        file!(), line!(), $msg, stringify!($val), &tmp);
                    tmp
                }
            }
        };
        ($msg:expr, $val:expr,) => { msg!($msg, $val) };
        ($msg:expr, $($val:expr),+ $(,)?) => {
            ($(msg!($msg, $val)),+,)
        };
    }

    #[macro_export]
    macro_rules! tabular {
        ($val:expr) => {
            lg_nl!(crate::dbg::Tabular($val))
        };
    }

    #[macro_export]
    macro_rules! boolean_table {
        ($val:expr) => {
            lg_nl!(crate::dbg::BooleanTable($val));
        };
    }

    #[macro_export]
    macro_rules! boolean_slice {
        ($val:expr) => {
            lg!(crate::dbg::BooleanSlice($val));
        };
    }

    use std::fmt::{Debug, Formatter};

    #[derive(Clone)]
    pub struct Tabular<'a, T: Debug>(pub &'a [T]);
    impl<'a, T: Debug> Debug for Tabular<'a, T> {
        fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
            for i in 0..self.0.len() {
                writeln!(f, "{:2} | {:?}", i, &self.0[i])?;
            }
            Ok(())
        }
    }

    #[derive(Clone)]
    pub struct BooleanTable<'a>(pub &'a [Vec<bool>]);
    impl<'a> Debug for BooleanTable<'a> {
        fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
            for i in 0..self.0.len() {
                writeln!(f, "{:2} | {:?}", i, BooleanSlice(&self.0[i]))?;
            }
            Ok(())
        }
    }

    #[derive(Clone)]
    pub struct BooleanSlice<'a>(pub &'a [bool]);
    impl<'a> Debug for BooleanSlice<'a> {
        fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
            write!(
                f,
                "{}",
                self.0
                    .iter()
                    .map(|&b| if b { "1 " } else { "0 " })
                    .collect::<String>()
            )?;
            Ok(())
        }
    }
}
// }}}

fn square_distance((x0, y0): &(i64, i64), (x1, y1): &(i64, i64)) -> i64 {
    (x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0)
}

fn main() {
    let mut buf = ngtio::Buffer::new();
    let n = buf.usize();
    let x_max = buf.i64();
    let y_max = buf.i64();
    let points = iter::repeat_with(|| (buf.i64(), buf.i64()))
        .take(n)
        .collect::<Vec<_>>();
    let valid_pairs = seq::cartesian_product(points.iter().cloned(), points.iter().cloned())
        .filter(|&(p0, p1)| {
            p0 != p1 && {
                let sq_dist = square_distance(&p0, &p1);
                let (x, y) = p0;
                [x, y, x_max - x, y_max - y]
                    .iter()
                    .all(|&d| sq_dist <= d * d)
            }
        })
        .collect::<Vec<_>>();
    let ans = seq::cartesian_product(valid_pairs.iter().cloned(), valid_pairs.iter().cloned())
        .filter(|&((p0, p1), (p2, p3))| {
            p0 != p2 && p0 != p3 && p1 != p2 && p1 != p3 && {
                let sq_r0 = square_distance(&p0, &p1);
                let sq_r1 = square_distance(&p2, &p3);
                let sq_d = square_distance(&p0, &p2);
                sq_d + sq_r1 < sq_r0 && 4 * sq_d * sq_r1 < (sq_r0 - sq_r1 - sq_d).pow(2)
            }
        })
        .count();
    println!("{}", ans);
}

提出情報

ジャッジ結果