本文主要是介绍vijos1883 月光的魔法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
背景
影几欺哄了众生了 天以外—— 月儿何曾圆缺 描述
有些东西就如同月光的魔法一般.
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 所有圆都是唯一的,不会出现重叠. 输出格式输出只有一行,要求输出平面被分割成了多少块.
正常情况下，一个圆只会多分出来一块，但是如果一个圆里恰有几个彼此相切的小圆，就会再把这个大圆上下分开。
所以可以离散化之后按半径排序，用线段树维护目前已经被小圆覆盖到的区间。对于一个圆，如果他的直径已经完全被覆盖，他对答案的贡献就是2，否则就是1。然后再用这个圆去覆盖。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct inter
{int l,r;bool operator < (const inter & iii) const{return r-l<iii.r-iii.l;}
}a[300010];
int ori_l[300010],ori_r[300010],ord[600010],lson[3000010],rson[3000010],con[3000010],tag[3000010],n,m,tot=1;
void down(int p)
{if (tag[p]){con[p]=1;tag[lson[p]]=tag[rson[p]]=1;tag[p]=0;}
}
void up(int p)
{down(p);down(lson[p]);down(rson[p]);if (con[lson[p]]==0&&con[rson[p]]==0)con[p]=0;else{if (con[lson[p]]==1&&con[rson[p]]==1)con[p]=1;else con[p]=2;}
}
void build(int p,int ll,int rr)
{if (ll==rr) return;int mid=(ll+rr)/2;lson[p]=++tot;build(tot,ll,mid);rson[p]=++tot;build(tot,mid+1,rr);
}
int find(int p,int ll,int rr,int l,int r)
{down(p);if (ll==l&&rr==r)return con[p]==1;int mid=(ll+rr)/2;if (r<=mid) return find(lson[p],ll,mid,l,r);if (l>mid) return find(rson[p],mid+1,rr,l,r);return find(lson[p],ll,mid,l,mid)==1&&find(rson[p],mid+1,rr,mid+1,r)==1;
}
void mark(int p,int ll,int rr,int l,int r)
{if (ll==l&&rr==r){tag[p]=1;return;}down(p);int mid=(ll+rr)/2;if (r<=mid) mark(lson[p],ll,mid,l,r);else{if (l>mid) mark(rson[p],mid+1,rr,l,r);else{mark(lson[p],ll,mid,l,mid);mark(rson[p],mid+1,rr,mid+1,r);}}up(p);
}
int main()
{int i,j,k,p,q,x,y,z,ans=1;scanf("%d",&n);for (i=1;i<=n;i++){scanf("%d%d",&x,&y);ord[++m]=ori_l[i]=x-y;ord[++m]=ori_r[i]=x+y;}sort(ord+1,ord+m+1);m=unique(ord+1,ord+m+1)-ord-1;for (i=1;i<=n;i++){a[i].l=lower_bound(ord+1,ord+m+1,ori_l[i])-ord;a[i].r=lower_bound(ord+1,ord+m+1,ori_r[i])-ord;}sort(a+1,a+n+1);build(1,1,m-1);for (i=1;i<=n;i++){if (find(1,1,m-1,a[i].l,a[i].r-1)==1) ans+=2;else ans++;mark(1,1,m-1,a[i].l,a[i].r-1);}printf("%d\n",ans);
}这篇关于vijos1883 月光的魔法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
