天神下凡(面分割)
问题 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;
}
/**/
