백준 10000 - 원 영역

원이 교차하지 않으므로 접하는 경우만 생각하면 됩니다.

원의 지름 끝이 원들에 의해 연결되어 있다면 영역이 2개로 나뉘고, 그 외의 경우에는 1개가 생깁니다.

연결성 확인은 서로소 집합 자료구조를 통해 쉽게 할 수 있지만, x좌표의 범위가 넓어 좌표 압축이 필요합니다.

압축에 O(NlogN), 죄표를 검색하는 데 O(logN), 연결성 확인에 O(log*N)이므로 O(NlogNlog*N)에 해결할 수 있습니다.

코드

use std::io::{stdin, Read};

fn main() {
    let mut input = String::new();
    stdin().read_to_string(&mut input).unwrap();
    let mut input = input.split_ascii_whitespace();
    let n = input.next().unwrap().parse().unwrap();
    let mut circles = Vec::with_capacity(n);
    let mut points = Vec::with_capacity(n * 2);
    for _ in 0..n {
        let xi: i32 = input.next().unwrap().parse().unwrap();
        let ri: u32 = input.next().unwrap().parse().unwrap();
        circles.push((xi + ri as i32, ri));
        points.push(xi + ri as i32);
        points.push(xi - ri as i32);
    }
    circles.sort_unstable();
    points.sort_unstable();
    points.dedup();
    let mut cuts = Sets::new(points.len());
    let mut count = 1;
    for (ei, ri) in circles {
        let s = points.binary_search(&(ei - (ri * 2) as i32)).unwrap();
        let e = points.binary_search(&ei).unwrap();
        let rs = cuts.root(s);
        let re = cuts.root(e);
        if rs == re {
            count += 2;
        } else {
            count += 1;
            cuts.join(rs, re);
        }
    }
    println!("{}", count);
}

struct Sets {
    up: Vec<usize>,
    rank: Vec<usize>,
}

impl Sets {
    fn new(n: usize) -> Self {
        Self {
            up: (0..n).collect(),
            rank: vec![1; n],
        }
    }

    fn root(&mut self, mut x: usize) -> usize {
        while x != self.up[x] {
            self.up[x] = self.up[self.up[x]];
            x = self.up[x];
        }
        x
    }

    fn join(&mut self, mut rx: usize, mut ry: usize) -> usize {
        if self.rank[rx] < self.rank[ry] {
            std::mem::swap(&mut rx, &mut ry);
        }
        self.up[ry] = rx;
        if self.rank[rx] == self.rank[ry] {
            self.rank[rx] += 1;
        }
        rx
    }
}