結果
| 問題 | No.96 圏外です。 |
| ユーザー |
 cotton_fn_
|
| 提出日時 | 2020-06-11 04:17:59 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 1,534 ms / 5,000 ms |
| コード長 | 7,726 bytes |
| コンパイル時間 | 15,446 ms |
| コンパイル使用メモリ | 404,952 KB |
| 実行使用メモリ | 16,012 KB |
| 最終ジャッジ日時 | 2024-06-24 01:39:38 |
| 合計ジャッジ時間 | 36,615 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 28 |
ソースコード
#![allow(unused_imports, unused_macros)]use kyoproio::*;use std::{collections::*,io::{self, prelude::*},iter,mem::{replace, swap},};fn main() -> io::Result<()> {std::thread::Builder::new().stack_size(64 * 1024 * 1024).spawn(solve)?.join().unwrap();Ok(())}fn solve() {let stdin = io::stdin();let mut kin = KInput::new(stdin.lock());let stdout = io::stdout();let mut out = io::BufWriter::new(stdout.lock());macro_rules! output { ($($args:expr),+) => { write!(&mut out, $($args),+).unwrap(); }; }macro_rules! outputln {($($args:expr),+) => { output!($($args),+); outputln!(); };() => { output!("\n"); if cfg!(debug_assertions) { out.flush().unwrap(); } }}let n: usize = kin.input();if n == 0 {outputln!("1");return;}let ps: Vec<_> = kin.iter::<(i32, i32)>().take(n).map(|(x, y)| [x, y]).collect();let map: HashMap<_, _> = ps.iter().enumerate().map(|(i, &p)| (p, i)).collect();let mut uf = UnionFind::new(n);for (i, &[x, y]) in ps.iter().enumerate() {for dx in -10..=10 {for dy in -10..=10 {if dx * dx + dy * dy <= 100 {if let Some(&j) = map.get(&[x + dx, y + dy]) {uf.unite(i, j);}}}}}let mut comps = vec![Vec::new(); n];for i in 0..n {comps[uf.root(i)].push(ps[i]);}let mut max = 0;for c in comps {if !c.is_empty() {// eprintln!("{:?}", &c);let (i, j) = farest_pair(&c);// eprintln!("{:?} - {:?}", c[i], c[j]);let [x1, y1] = c[i];let [x2, y2] = c[j];let x = x2 - x1;let y = y2 - y1;max = max.max(x * x + y * y);}}let ans = 2. + (max as f64).sqrt();outputln!("{}", ans);}use std::ops;pub fn graham_scan<T>(ps: &[[T; 2]]) -> Vec<usize>whereT: PartialOrd + ops::Sub<Output = T> + ops::Mul<Output = T> + Copy,{let mut ids: Vec<_> = (0..ps.len()).collect();ids.sort_by(|&i, &j| ps[i].partial_cmp(&ps[j]).unwrap());let mut hull: Vec<usize> = Vec::new();for dir in 0..2 {let mut len = dir;for &i in &ids {let [x2, y2] = ps[i];while len >= 2 {let [x0, y0] = ps[hull[hull.len() - 2]];let [x1, y1] = ps[hull[hull.len() - 1]];if (x1 - x0) * (y2 - y0) >= (x2 - x0) * (y1 - y0) {break;}hull.pop();len -= 1;}hull.push(i);len += 1;}ids.pop();ids.reverse();ids.pop();}hull}pub fn farest_pair<T>(ps: &[[T; 2]]) -> (usize, usize)whereT: PartialOrd + ops::Add<Output = T> + ops::Sub<Output = T> + ops::Mul<Output = T> + Copy,{let norm = |[x0, y0]: [T; 2], [x1, y1]: [T; 2]| (x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0);let hull = graham_scan(ps);let mut res = (0, 0);let mut max = None;let mut j = 0;for &i in &hull {let mut d = norm(ps[i], ps[hull[j]]);loop {let j_inc = if j + 1 < hull.len() { j + 1 } else { 0 };let d_inc = norm(ps[i], ps[hull[j_inc]]);if d >= d_inc {break;}d = d_inc;j = j_inc;}if Some(d) > max {max = Some(d);res = (i, hull[j]);}}res}pub struct UnionFind {p: Vec<isize>,}impl UnionFind {pub fn new(n: usize) -> Self {Self { p: vec![-1; n] }}pub fn root(&self, mut u: usize) -> usize {while self.p[u] >= 0 {u = self.p[u] as usize;}u}pub fn size(&self, u: usize) -> usize {(-self.p[self.root(u)]) as usize}pub fn unite(&mut self, u: usize, v: usize) -> bool {let mut u = self.root(u);let mut v = self.root(v);if u == v {return false;}if self.p[u] > self.p[v] {swap(&mut u, &mut v);}self.p[u] += self.p[v];self.p[v] = u as isize;true}pub fn is_same(&self, u: usize, v: usize) -> bool {self.root(u) == self.root(v)}}// -----------------------------------------------------------------------------pub mod kyoproio {use std::io::prelude::*;pub trait Input {fn str(&mut self) -> &str;fn input<T: InputParse>(&mut self) -> T {T::input(self)}fn iter<T: InputParse>(&mut self) -> Iter<T, Self> {Iter(self, std::marker::PhantomData)}fn seq<T: InputParse, B: std::iter::FromIterator<T>>(&mut self, n: usize) -> B {self.iter().take(n).collect()}}pub struct KInput<R> {src: R,buf: String,pos: usize,}impl<R: BufRead> KInput<R> {pub fn new(src: R) -> Self {Self {src,buf: String::with_capacity(1024),pos: 0,}}pub fn src(&mut self) -> &mut R {&mut self.src}}impl<R: BufRead> Input for KInput<R> {fn str(&mut self) -> &str {loop {if self.pos >= self.buf.len() {self.pos = 0;self.buf.clear();if self.src.read_line(&mut self.buf).expect("io error") == 0 {return &self.buf;}}let range = self.pos..self.buf[self.pos..].find(|c: char| c.is_ascii_whitespace()).map(|i| i + self.pos).unwrap_or_else(|| self.buf.len());self.pos = range.end + 1;if range.end > range.start {return &self.buf[range];}}}}pub struct Iter<'a, T, I: ?Sized>(&'a mut I, std::marker::PhantomData<*const T>);impl<'a, T: InputParse, I: Input + ?Sized> Iterator for Iter<'a, T, I> {type Item = T;fn next(&mut self) -> Option<T> {Some(self.0.input())}}pub trait InputParse: Sized {fn input<I: Input + ?Sized>(src: &mut I) -> Self;}impl InputParse for Vec<u8> {fn input<I: Input + ?Sized>(src: &mut I) -> Self {src.str().as_bytes().to_owned()}}macro_rules! from_str_impl {{ $($T:ty)* } => {$(impl InputParse for $T {fn input<I: Input + ?Sized>(src: &mut I) -> Self {src.str().parse::<$T>().expect("parse error")}})*}}from_str_impl! {String char bool f32 f64 isize i8 i16 i32 i64 i128 usize u8 u16 u32 u64 u128}macro_rules! tuple_impl {($H:ident $($T:ident)*) => {impl<$H: InputParse, $($T: InputParse),*> InputParse for ($H, $($T),*) {fn input<I: Input + ?Sized>(src: &mut I) -> Self {($H::input(src), $($T::input(src)),*)}}tuple_impl!($($T)*);};() => {}}tuple_impl!(A B C D E F G);#[macro_export]macro_rules! kdbg {($($v:expr),*) => {if cfg!(debug_assertions) { dbg!($($v),*) } else { ($($v),*) }}}}