vijos 天神下凡 - NekoMio's Blog

题目描述#

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

题解#

那个栈扫一遍

1
#include <cstdio>
2
#include <cstring>
3
#include <stack>
4
#include <algorithm>
5
using namespace std;
6
struct data
7
{
8
    int l, r, id;
9
    bool operator<(const data &a) const
10
    {
11
        return l == a.l ? r > a.r : l < a.l;
12
    }
13
} a[1000001];
14
int main(int argc, char const *argv[])
15
{
16
    stack<data> st;
17
    int n, s, r;
18
    scanf("%d", &n);
19
    for (int i = 0; i < n; i++)
20
    {
21
        scanf("%d%d", &s, &r);
22
        a[i].l = s - r, a[i].id = i, a[i].r = s + r;
23
    }
24
    sort(a, a + n);
25
    // for (int i = 0; i < n; i++)
26
    // {
27
    //     printf("%d %d %d\n", a[i].l, a[i].r, a[i].id);
28
    // }
29
    //while (1)
30
        ;
31
    int ans = 0;
32
    for (int i = 0; i < n; i++)
33
    {
34
        if (a[i].l == a[i + 1].l && i + 1 != n - 1)
35
        {
36
            st.push(a[i]);
37
            continue;
38
        }
39
        if (!st.empty() && a[i].r == st.top().r)
40
        {
41
            st.pop();
42
            ans++;
43
        }
44
        if (a[i].r != a[i + 1].l)
45
        {
46
            if (!st.empty())
47
                st.pop();
48
        }
49
    }
50
    printf("%d", ans + n + 1);
51
    return 0;
52
}