469 字
2 分钟
vijos 天神下凡
2017-07-30

题目描述#

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;
}
vijos 天神下凡
https://www.nekomio.com/posts/48/
作者
NekoMio
发布于
2017-07-30
许可协议
CC BY-NC-SA 4.0