输入数据第一行:输出一个整数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 #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 }