P6875 [COCI2013-2014#6] KRUŽNICE

· · 题解

题目大意

有 n 个互不相交的圆（可以相切），第 i 个圆圆心为 (x_i,0)，半径为 r，求这些圆平面分成了几个部分。

题解

据我所知，本题共有 3 个做法。

Sol1. 单调栈

首先，我们观察到每加入一个圆，至少多分了 1 个部分，但也有时候分成了两个部分，即大圆被若干个小圆分成上下两部分。

那么我们考虑如何统计这种特殊情况。

首先，我们按每个圆的右端点从小到大排序，然后，我们按顺序加入单调栈中。

那么如果一个大圆里面的小圆没有再包含一个圆，我们就可以直接记录这个大圆包含的小圆的直径和，与大圆的直径比较就可以判断是否为特殊情况。

那么我们考虑维护一个没有包含关系的栈。

因为我们把右端点从小到大排了序，所以在加入一个圆的时候，我们只要看左端点，如果刚加的这个圆的左端点小于等于栈顶的左端点，那么栈顶的圆就被包含了，我们把它弹出，顺便记录弹出圆的直径和。

于是我们这个左端点递增的单调栈，既可以保证没有二次包含关系，也可以实时统计大圆包含的小圆的直径和，直接判断即可。

时间复杂度为 \Theta(n\log n)，瓶颈在排序上。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PII pair<int, int>
#define mkp make_pair
#define INF INT_MAX
template <typename T> inline void rd(T &x){
    x = 0; bool f = true; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') f = false; ch = getchar();}
    while(ch >= '0' && ch <= '9'){ x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar();}
    if(!f) x = -x;
}
template <typename T, typename ...Args> inline void rd(T &x, Args &...args){ rd(x); rd(args...);}
const int N = 3e5 + 10;
struct circle {
    int x, r;
}c[N];
bool cmp(circle A, circle B) {
    if(A.x + A.r != B.x + B.r) return A.x + A.r < B.x + B.r;
    else return A.x - A.r > B.x - B.r;
}
int n, st[N], top, ans;
int main() {
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    rd(n);
    for(int i = 1; i <= n; ++i) rd(c[i].x, c[i].r);
    sort(c + 1, c + n + 1, cmp);
    for(int i = 1; i <= n; ++i) {
        int now = c[i].x - c[i].r, sum = 0;
        while(c[st[top]].x - c[st[top]].r >= now && top >= 1) {
            sum += 2 * c[st[top]].r;
            top --;
        }
        st[++top] = i;
        if(sum == 2 * c[i].r) ans ++;
    }
    cout << ans + n + 1 << endl;
    return 0;
}

Sol2.并查集

首先回到统计大圆被小圆分割成上下两个部分的情况数。

我们如果在按半径加入圆的时候，把它的左右端点连一条边，那么在加入大圆的时候，如果大圆的左右端点已经连通了，那么这个大圆一定被小圆分割成上下两部分了。

因为坐标很大，并且可能是负数，所以离散化后并查集即可。

复杂度为 \Theta(n \log n)。

Sol3.线段树

继续回到统计大圆被小圆分割成上下两个部分的情况数。

按半径加入圆的时候，我们在这个圆的两个端点进行一次区间 +1，那么如果大圆左右端点的区间的区间最小值为 0，那说明没有被完全分开，否则被完全分开。

这里依然要离散化。

复杂度为 \Theta(n \log n)。

注意，Sol2 和 Sol3 中的做法需要注意，线段树和并查集只能维护整点的信息，所以我们将左端点 +1，或者右端点 -1，来保证不会有形如 (i,0) 在一个圆，(i+1,0) 在另一个圆，就算中间有空隙，也不会被计算到的情况。

线段树代码：Paste。