[Vijos1883] 月光的魔法

2014-10-31
竞赛题解 / 模拟
Vijos

背景 Background

影几欺哄了众生了

天以外——

月儿何曾圆缺

描述 Description

有些东西就如同月光的魔法一般.

Luke 是爱着 vijos 的.

他想为自己心爱的东西画些什么.

就画 N 个圆吧.

把它们的圆心都固定在 x 轴上.

圆与圆.

为了爱, 两两不能相交.

为了爱, 它们可以互相贴在一起.

内切或外切, 都是允许的.

vijos 的美丽, 在于人心.

vijos 的孩子们, 一定能告诉大家: Luke 画的圆究竟把平面分割成了多少块?

月光恬美地洒在大地上.

Luke 知道, 如果什么都不画, 平面就只有一块. 多美呢!

Luke 知道, 只画一个圆, 平面就分成了两块. 也很美呢!

但 Luke 还是要多画一些的, 因为他真的深爱着 vijos 呢.

输入格式 InputFormat

输入数据第一行: 输出一个整数 N,1<=N<=300,000. 表示圆的个数.
之后 N 行, 每一行有 2 个整数, x[i] 和 r[i] 表示圆心固定在 x[i] 的位置, 半径为 r[i].
-1,000,000,000<=x[i]<=1,000,000,000
1<=r[i]<=1,000,000,000
所有圆都是唯一的, 不会出现重叠.

输出格式 OutputFormat

输出只有一行, 要求输出平面被分割成了多少块.

样例输入 SampleInput

4
7 5
-9 11
11 9
0 20

样例输出 SampleOutput

6

Vijos 1883

代码 Code

按照端点大小排序，找到每个圆的包含它的最近的圆，用长度来判断是否圆圆相切将大圆分成两部分。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
struct circle
{
    int l,r,x,inl;
    bool operator < (const circle &temp) const
    {
        return (l==temp.l)?(r>temp.r):(l<temp.l);
    }
}a[300005];
int ans;
int fa[300005];
inline void read(int &x)
{
    x=0;char ch=getchar();
    while (ch<'0' || ch>'9') ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
void find(int s)
{
    int i,j,t;
    for (i=s+1;a[i].r<=a[s].r && i<=n;i++) if (!fa[i])
    {
        fa[i]=s;
        find(i);
    }
}
int main()
{
    //freopen("god.in","r",stdin);
    //freopen("god.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d%d",&x,&r),a[i].l=x-r,a[i].r=x+r,a[i].x=x;
    sort(a+1,a+n+1);
    ans=n+1;
    for (i=1;i<=n;i++) if (!fa[i]) find(i);
    for (i=1;i<=n;i++) a[fa[i]].inl+=a[i].r-a[i].l;
    for (i=1;i<=n;i++) if (a[i].inl==a[i].r-a[i].l) ans++;
    printf("%d\n",ans);
    return 0;
}