学步园

由一些圆心都在x轴上的圆，任意两个圆的关系只会是内含，内切，外切，外离。求圆把平面分成多少个部分。

题目做法据说很多，仅知道其中两种：栈和并查集。

首先对圆进行排序，优先左端点位置，然后是半径长度。然后从左到右扫描一遍。

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
#define MAXN 300100
#define LL long long
#define INF 1000000100

struct Circle
{
    LL l, r, cnt, cap;
    Circle() {}
    Circle(LL _l, LL _r, LL _cnt, LL _cap):
        l(_l), r(_r), cnt(_cnt), cap(_cap){}
    bool operator <(const Circle &argu) const
    {
        if(l == argu.l)
            return argu.r < r;
        else
            return l < argu.l;
    }
    void out()
    {
        printf("%I64d %I64d %I64d %I64d\n", l, r, cnt, cap);
    }
}cc[MAXN];

int n, ctop;
LL x, r;
int s[MAXN];

int main()
{
    //freopen("1883.in", "r", stdin);

    scanf("%d", &n);

    cc[0] = Circle(-INF, (LL)2 * INF, (LL)1, (LL)3 * INF);
    for(int i = 1; i <= n; i++)
    {
        scanf("%I64d%I64d", &x, &r);
        cc[i] = Circle(x - r, x + r, (LL)1, (LL)2 * r);
    }

    n++;
    sort(cc, cc + n);

    ctop = s[0] = 0;
    for(int i = 1; i < n; i++)
    {
        while(cc[i].l >= cc[s[ctop]].r)
        {
            if(cc[s[ctop]].cap == 0)
                cc[s[ctop]].cnt++;
            cc[s[ctop - 1]].cnt += cc[s[ctop]].cnt;
            ctop--;
        }
        cc[s[ctop]].cap -= cc[i].r - cc[i].l;
        s[++ctop] = i;
    }

    while(ctop > 0)
    {
        if(cc[s[ctop]].cap == 0)
            cc[s[ctop]].cnt++;
        cc[s[ctop - 1]].cnt += cc[s[ctop]].cnt;
        ctop--;
    }

    printf("%I64d\n", cc[0].cnt);

    return 0;
}