voijs1883 月光的魔法

浏览数：35 / 时间：2015年06月09日

背景

影几欺哄了众生了
天以外——
月儿何曾圆缺

描述

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

Luke是爱着vijos的.
他想为自己心爱的东西画些什么.

就画N个圆吧.
把它们的圆心都固定在x轴上.

圆与圆.
为了爱,两两不能相交.
为了爱,它们可以互相贴在一起.
内切或外切,都是允许的.

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

月光恬美地洒在大地上.
Luke知道,如果什么都不画,平面就只有一块.多美呢!
Luke知道,只画一个圆,平面就分成了两块.也很美呢!
但Luke还是要多画一些的,因为他真的深爱着vijos呢.

格式

输入格式

输入数据第一行:输出一个整数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
所有圆都是唯一的,不会出现重叠.

输出格式

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

样例1

样例输入1

2
1 3
5 1

样例输出1

样例2

样例输入2

样例输出2

样例3

样例输入3

样例输出3

限制

对于40%的数据:
N<=5000.
对于100%的数据:
1<=N<=300,000;-1,000,000,000<=x[i]<=1,000,000,000;1<=r[i]<=1,000,000,000

考虑圆对答案的贡献：当它并没有被沿着直径分开的时候，对答案的贡献是1。如果被分开贡献是2。所以按r从小到大排序，把树的左右端点离散，用一个线段树维护区间是否被覆盖。如果已经被覆盖，贡献是2，否则贡献是1。

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<cstdlib>
  5 #include<algorithm>
  6 #include<cmath>
  7 #include<queue>
  8 #include<deque>
  9 #include<set>
 10 #include<map>
 11 #include<ctime>
 12 #define LL long long
 13 #define N 500010
 14 #define mod 1000007
 15 using namespace std;
 16 struct yuan{int x,r,left,right;}a[N];bool operator <(const yuan &a,const yuan &b){return a.r<b.r;}
 17 struct ha{int v,next,rnk;}hash[3*N];bool operator <(const ha &a,const ha &b){return a.v<b.v;}
 18 struct segtree{int l,r;bool mark;}tree[8*N];
 19 LL ans;
 20 int n;
 21 int head[mod];
 22 int cnt,mx;
 23 int from[3*N];
 24 inline int ins(int w)
 25 {
 26     int u=w%mod;if (u<0)u+=mod;
 27     for (int i=head[u];i;i=hash[i].next)
 28       if (hash[i].v==w) return i;
 29     hash[++cnt].v=w;
 30     hash[cnt].next=head[u];
 31     hash[cnt].rnk=cnt;
 32     head[u]=cnt;
 33     return cnt;
 34 }
 35 inline void build(int now,int l,int r)
 36 {
 37     tree[now].l=l;
 38     tree[now].r=r;
 39     if (l==r)return;
 40     int mid=(l+r)>>1;
 41     build(now<<1,l,mid);
 42     build(now<<1|1,mid+1,r);
 43 }
 44 inline void update(int k)
 45 {tree[k].mark=tree[k<<1].mark&&tree[k<<1|1].mark;}
 46 inline bool query(int now,int l,int r)
 47 {
 48     int x=tree[now].l,y=tree[now].r;
 49     if (x==l&&y==r)return tree[now].mark;
 50     int mid=(x+y)>>1;
 51     if (r<=mid)return query(now<<1,l,r);
 52     else if (l>mid)return query(now<<1|1,l,r);
 53     else return query(now<<1,l,mid)&&query(now<<1|1,mid+1,r);
 54 }
 55 inline void mark(int now,int l,int r)
 56 {
 57     int x=tree[now].l,y=tree[now].r;
 58     if (x==l&&y==r)
 59     {
 60         tree[now].mark=1;
 61         return;
 62     }
 63     int mid=(x+y)>>1;
 64     if (r<=mid)mark(now<<1,l,r);
 65     else if (l>mid)mark(now<<1|1,l,r);
 66     else
 67     {
 68         mark(now<<1,l,mid);
 69         mark(now<<1|1,mid+1,r);
 70     }
 71     update(now);
 72 }
 73 int main()
 74 {
 75     //freopen("god7.in","r",stdin);
 76     //freopen("god .ans","w",stdout);
 77     scanf("%d",&n);
 78     for(int i=1;i<=n;i++)
 79     {
 80         scanf("%d",&a[i].x);
 81         scanf("%d",&a[i].r);
 82         a[i].left=ins(a[i].x-a[i].r);
 83         a[i].right=ins(a[i].x+a[i].r);
 84     }
 85     sort(hash+1,hash+cnt+1);
 86     for (int i=1;i<=cnt;i++)
 87       from[hash[i].rnk]=i;
 88     for (int i=1;i<=n;i++)
 89     {
 90       a[i].left=from[a[i].left];
 91       a[i].right=from[a[i].right];
 92       if (a[i].right>mx)mx=a[i].right;
 93     }
 94     sort(a+1,a+n+1);
 95     build(1,1,mx);
 96     ans=n+1;
 97     for (int i=1;i<=n;i++)
 98       {
 99           if (query(1,a[i].left,a[i].right-1))ans++;
100           mark(1,a[i].left,a[i].right-1);
101       }
102     printf("%I64d\n",ans);
103 }