「NOI考前欢乐赛」小奇画画
画楼处
是谁衣白衫如初
谁红裳如故
——《忆红莲》
「问题描述」
小奇想画几朵红莲，可惜它刚开始学画画，只能从画圆开始。小奇画了n个圆，它们的圆心都在x轴上，且两两不相交（可以相切）。现在小奇想知道，它画的圆把画纸分割成了多少块？（假设画纸无限大）
「输入格式」
第一行包括1个整数n。
接下来n行，每行两个整数x，r，表示小奇画了圆心在（x，0），半径为r的一个圆。
「输出格式」
输出一个整数表示答案。
「样例输入」
4
7 5
-9 11
11 9
0 20
「样例输出」
6
「数据范围」
对于30%数据，n<=5000；
对于100%数据，1<=n<=300000,-10^9<=x<=10^9,1<=r<=10^9。
题解
本题加强自vijos 月光的魔法 「NOIP模拟赛」天神下凡
zhber：
考虑圆对答案的贡献：当它并没有被沿着直径分开的时候，对答案的贡献是1。如果被分开贡献是2。所以按r从小到大排序，把树的左右端点离散，用一个线段树维护区间是否被覆盖。如果已经被覆盖，贡献是2，否则贡献是1
我的做法：
在一般情况n个圆划分出n+1个平面
对圆进行排序以后，用栈处理出每个圆的一级祖先形成一棵树
若一个结点的儿子的圆的直径与其相等，说明它的儿子首尾相接把它割成了两部分，多形成一个平面，这个直接搜索
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define ll long long #define inf 2147483647 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,cnt,ans,top,t; int q[300005],last[300005]; struct data{int l,r;}a[300005]; struct edge{int to,next;}e[300005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; } bool operator<(data a,data b) { return a.l<b.l||(a.l==b.l&&a.r>b.r); } void bfs() { int head=0,tail=1; q[0]=0; while(head!=tail) { int now=q[head];head++; ll sum=0; for(int i=last[now];i;i=e[i].next) { sum+=a[e[i].to].r-a[e[i].to].l; q[tail++]=e[i].to; } if(sum==a[now].r-a[now].l)ans++; } } void build() { int now=-inf; now=a[t].l; while(top&&a[q[top]].r<=now)top--; if(a[t].l==now) { insert(q[top],t); q[++top]=t; t++; } } int main() { n=read(); for(int i=1;i<=n;i++) { int x=read(),r=read(); a[i].l=x-r;a[i].r=x+r; } sort(a+1,a+n+1); ans=n+1; t=1; while(t<=n)build(); bfs(); printf("%d\n",ans); return 0; } |
Subscribe
计数器 9774563
OI 课件=>
OI 课件=>