Gym - 100781G Goblin Garden Guards （扫描线）

题意：

n 只哥布林，每只哥布林都有一个位置坐标。

m 个炮台，每个炮台都有一个位置坐标和一个攻击半径。

如果一个哥布林在任何一个炮台的攻击范围内，都会被杀死。

求最后没有被杀死的哥布林的数量。

这题暴力加一些小小的优化可以爆过去。。。然后场上并不敢试。

标算是扫描线。炮台攻击范围内的每个横坐标都拉一个扫描线，把线的两端的点和哥布林的点一起加进一个数组。

然后排序，就会发现能被杀死的哥布林的点在一根线的两个端点之间。

直接扫一遍统计答案就可以了。注意存点的数组要开够。

另外就是。。。排序的时候 y 坐标从小到大排序就 WA，改成从大到小就A了。。我也不知道为啥。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

using namespace std;

#define maxn 9000000 + 1000

struct Node

{

    int x, y, type;

    Node(int xx, int yy, int tt) : x(xx), y(yy), type(tt) {}

    Node() {}

}a[maxn];

bool cmp(Node a, Node b)

{

    if (a.x != b.x) return a.x < b.x;

    if (a.y != b.y) return a.y > b.y;

    return a.type > b.type;

}

int getdis(int x, int y)

{

    return round(floor(sqrt(x*x - y*y)));

}

int tot = ;

int main()

{

    int n;

    scanf("%d", &n);

    for (int i = ; i <= n; i++)

    {

        tot++;

        scanf("%d%d", &a[tot].x, &a[tot].y);

        a[tot].type = ;

    }

    int m;

    scanf("%d", &m);

    for (int i = ; i <= m; i++)

    {

        int x, y, r;

        scanf("%d%d%d", &x, &y, &r);

        for (int j = -r; j <= r; j++)

        {

            a[++tot] = Node(x+j, y+getdis(r, j), );

            a[++tot] = Node(x+j, y-getdis(r, j), -);

        }

    }

    sort(a+, a++tot, cmp);

    int sum = , ans = ;

    for (int i = ; i <= tot; i++)

    {

        sum += a[i].type;

        if (a[i].type ==  && sum != )

            ans++;

    }

    printf("%d\n", n - ans);

}

巴特西

Gym - 100781G Goblin Garden Guards （扫描线）

最新文章

热门文章