小奇画画(对于容器的使用)

小奇画画

时间限制: 1 Sec  内存限制: 128 MB

题目描述

红莲清泪两行欲吐半点却无
如初是你杳然若绯雾还在水榭畔画楼处
是谁衣白衫如初谁红裳如故
——《忆红莲》

小奇想画几朵红莲，可惜它刚开始学画画，只能从画圆开始。小奇画了n个圆，它们的圆心都在x轴上，且两两不相交（可以相切）。现在小奇想知道，它画的圆把画纸分割成了多少块？（假设画纸无限大）

输入

第一行包括1个整数n。
接下来n行，每行两个整数x，r，表示小奇画了圆心在（x，0），半径为r的一个圆。

输出

输出一个整数表示答案。

样例输入

复制样例数据

4 
7 5 
-9 11 11 9 
0 20

样例输出

6

提示

对于 100%数据，1<=n<=300000,-10^9<=x<=10^9,1<=r<=10^9。

先将所有圆的区间和区间的距离算出来，根据左区间小，右区间大来排。然后遍历一遍，因为没有圆相交，所以后一个圆要么在前一个圆外面，要么就在前一个圆里面，如果在里面，记录下大圆被小圆站了多少距离，如果大圆被小圆占领的距离正好等于大圆的直径，那么就被分成两份。

PS：有n个圆肯定至少把平面分为n+1部分。

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n, f[300005];

struct node
{
	int l, r, num;
	bool operator <(const node &x)const{
		return l == x.l ? r > x.r : l < x.l;
	}
}a[300005];

stack<int> st;

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &n);
	int x, R;
	for (int i = 1; i <= n; i++){
		scanf("%d %d", &x, &R);
		a[i].l = x - R, a[i].r = x + R;
		a[i].num = 2 * R;
	}
	sort(a + 1, a + 1 + n);
	st.push(1);
	for (int i = 2; i <= n; i++){
		while(st.size() && a[st.top()].r < a[i].r) st.pop();
		if(st.size()) f[st.top()] += a[i].num;
		st.push(i);
	}
	int ans = n + 1;
	for (int i = 1; i <= n; i++){
		//cout << f[i] << endl;
		if(f[i] == a[i].num) ans++;
	}
	printf("%d\n", ans);

	return 0;
}
/**/