天神下凡(面分割)

问题 G: 天神下凡

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

题目描述

Czy找到宝藏获得屠龙宝刀和神秘秘籍！现在他要去找经常ntr他的Jmars报仇……
Czy学会了一招“堕天一击”，他对一个地点发动堕天一击，地面上就会留下一个很大的圆坑。圆坑的周围一圈能量太过庞大，因此无法通过。所以每次czy发动技能都会把地面分割。Jmars拥有好大好大的土地，几十眼都望不到头，所以可以假设土地的大小是无限大。现在czy对他发动了猛烈的攻击，他想知道在泽宇攻击之后他的土地被切成几份了?
Czy毕竟很虚，因此圆心都在x坐标轴上。另外，保证所有圆两两之间不会相交。

输入

输入第一行为整数n，表示czy放了n次堕天一击。
接下来n行，每行两个整数x[i]，r[i]。表示在坐标（x[i] , 0）放了一次堕天一击，半径为r[i]。

输出

输出一行，表示地面被分割成几块。

样例输入

4
7 5
-9 11
11 9
0 20

样例输出

6

提示

对于30%数据，n<=5000
对于100%数据，1<=n<=300000,-10^9<=x[i]<=10^9,1<=r[i]<=10^9.

/**/
#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];

int sum[300005];

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

stack<node> st;

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

	scanf("%d", &n);
	int p, r;
	for (int i = 1; i <= n; i++){
		scanf("%d %d", &p, &r);
		a[i].l = p - r, a[i].r = p + r;
	}
	sort(a + 1, a + 1 + n);//将每个圆表示成线段，然后根据左小右大的顺序排序
	for (int i = 1; i <= n; i++){
		f[i] = i;
		a[i].id = i;
	}
	for (int i = 1; i <= n; i++){//求出各个圆被什么圆包围，是最小包围的圆，不是最外面的圆
		if(st.empty()){
			st.push(a[i]);
		}else{
			while(st.size()){
				node t = st.top();
				if(t.l <= a[i].l && a[i].r <= t.r){//如果别包围，标记
					f[i] = t.id;
					break;
				}else{
					st.pop();//否则找是否有包围它的圆，如果没有，出栈
					continue;
				}
			}
			st.push(a[i]);
		}
	}
	int ans = n + 1;
	for (int i = 1; i <= n; i++){
		if(f[i] != i){
			sum[f[i]] += a[i].r - a[i].l;
			if(sum[f[i]] == a[f[i]].r - a[f[i]].l) ans++;//因为没有相交的圆，所以如果多个圆的直径和恰好等于大圆，那么大圆的面就被分为2部分
		}
	}
	printf("%d\n", ans);

	return 0;
}
/**/