[BOJ 10000]

문제 바로가기 : https://www.acmicpc.net/problem/10000
문제 설명은 위 링크에서 확인해주시길 바랍니다.

solution

review

기본적으로 원이 생길 때마다 영역이 1개씩 늘게 된다. 원 내부를 다른 원들이 채우면 1개 더 즉, 2개가 늘게 된다.
지금 다루는 원의 범위와 기준이 되는 범위(l, r) 그리고 원이 옆의 원과 연결되어 있는지(left) 체크해야 한다.
x좌표와 반지름값을 그대로 넣어도 되지만 범위를 가지고 놀거기 때문에 x-r, x+r을 넣어줬다.
스위핑을 위해 입력받은 값들을 왼쪽에 있는 것부터, 왼쪽 범위가 같다면 크기가 큰것이 먼저 오도록 정렬해주자.

bool cmp(const cir& a, const cir& b) {
    return a.l == b.l ? a.r > b.r : a.l < b.l;
}
...

int n; cin >> n;

for (int i = 0; i < n; i++) {
    int x, r; cin >> x >> r;
    circle.push_back({ x - r, x + r, false });
}
sort(circle.begin(), circle.end(), cmp);

서두에서 기본적으로 원이 생길 때마다 영역이 1개씩 늘게 된다고 했었다. 원이 n개면 영역은 최소 n+1개다.
작은 원들이 큰 원을 채워서 영역이 구분될 때만 답을 1씩 추가시킬 것이다.
원을 왼쪽부터 그리고 시작 위치가 같다면 크기순으로 정렬됐기 때문에 다룰 케이스가 많지 않다.
범위(l, r)에 원이 포함되는지 포함되지 않는지로 크게 2가지로 나눌 수 있다.
포함되지 않는다면 스택에서 현재 원(circle[i])을 포함하는 원이 나올 때까지 pop한다.
그리고 큰 원이 다른 원들로 채워졌는지(left && r == circle[i].r) 여부를 체크해서 답을 갱신한다.
모든 과정을 거친 후에는 스택에 담고, 현재 원의 범위가 다음 차례의 기준이 될 수 있도록 만들어주자.

이 때 left는 원이 계속 연결되어 왔는지 체크하기 위해서 만들었다.
현재 원의 왼쪽(circle[i].l)과 이전 원의 오른쪽(r)이 연결됐다면 이들을 포함하는 원의 left를 가져온다.
연결이 안됐다면 원이 채워지지 않았음을 의미하므로 false로 설정해준다.

ll ans = n + 1;
bool left = false;
int l = INF, r = -INF;
for (int i = 0; i < n; i++) {
   //원 안에 포함될 때
   if (l <= circle[i].l && circle[i].r <= r) {
       if (l == circle[i].l) left = true;
       if (left && r == circle[i].r) ans++;
   }
   //포함되지 않을 때
   else {
       //포함하는 원이 나올 때 까지 꺼내기
       while (!(l <= circle[i].l && circle[i].r <= r)) {
           if (s.empty()) {
               l = INF; r = -INF; left = false;
               break;
           }
           left = circle[i].l == r ? s.top().left : false; //왼쪽 원과의 연결 여부
           l = s.top().l; r = s.top().r; s.pop();
       }

       //꺼낸 원의 범위에 포함될 때
       if (l <= circle[i].l && circle[i].r <= r) {
           if (l == circle[i].l) left = true;
           if (left && r == circle[i].r) ans++;
       }
   }
   s.push({ l, r, left });
   l = circle[i].l; r = circle[i].r; left = false;
}

가슴 아프다😥