vijos 天神下凡

题目描述

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

题解

那个栈扫一遍

#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
struct data
{
    int l, r, id;
    bool operator<(const data &a) const
    {
        return l == a.l ? r > a.r : l < a.l;
    }
} a[1000001];
int main(int argc, char const *argv[])
{
    stack<data> st;
    int n, s, r;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d", &s, &r);
        a[i].l = s - r, a[i].id = i, a[i].r = s + r;
    }
    sort(a, a + n);
    // for (int i = 0; i < n; i++)
    // {
    //     printf("%d %d %d\n", a[i].l, a[i].r, a[i].id);
    // }
    //while (1)
        ;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (a[i].l == a[i + 1].l && i + 1 != n - 1)
        {
            st.push(a[i]);
            continue;
        }
        if (!st.empty() && a[i].r == st.top().r)
        {
            st.pop();
            ans++;
        }
        if (a[i].r != a[i + 1].l)
        {
            if (!st.empty())
                st.pop();
        }
    }
    printf("%d", ans + n + 1);
    return 0;
}