13045: 【原3045】大鱼

题目

题目描述

author: cnx 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3045

Description

cnx最近发现了一种奇怪的鱼，他有着奇怪的攻击方式，例如如果有一条鱼位于\((x_1,y_1)\)，它能攻击到所有满足\( (x-x_1)^2+(y-y_1)^2 \leq r^2 \)的所有\((x,y)\)，其中r是这条鱼的攻击距离。作为一只生命值只有1的渣渣，cnx想问一下地图上哪些地方是不安全的（能被某条鱼攻击到）。

Input Format

第一行三个数，n、m、k分别代表地图长、宽，以及现在有多少条鱼。
接下来每一行描述一条鱼，(x,y,r)分别代表所处位置以及攻击距离。其中 1<=x<=n,1<=y<=m 。

Output Format

输出一个数代表有多少个格子不安全。

Sample Input

3 3 1
2 2 1

Sample Output

5

About Testdata

60% 1<=n<=100
100% 1<=n<=1,000, 1<=k<=5000

Limits

Time limit: 1000ms, memory limit: 50000kb.

FineArtz's solution

/* 大鱼 */
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

class Fish{
public:
    //constructor
    Fish() : x(0), y(0), r(0) {};
    Fish(const Fish& f) : x(f.x), y(f.y), r(f.r) {};
    Fish(const int &xx, const int &yy, const int &rr) : x(xx), y(yy), r(rr) {};

    int x, y, r;
};
inline bool cmp(const Fish &f1, const Fish &f2){
    if (f1.y < f2.y) return true;
        if (f1.y == f2.y && f1.x < f2.x) return true;
        return false;
}

int unsafe[1005] = {0};
int ans = 0;
Fish fish[5005];

class Interval{
public:
    //constructor
    Interval() : l(0), r(0) {}
    Interval(int x, int y) : l(x), r(y) {}
    Interval(const Interval &i) : l(i.l), r(i.r) {}

    int l, r;
};
inline bool comp(Interval i1, Interval i2){
    return (i1.l < i2.l || i1.l == i2.l && i1.r > i2.r);
}

int main(){
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < k; ++i){
        cin >> fish[i].x >> fish[i].y >> fish[i].r;
    }
    sort(fish, fish + k, cmp);
    for (int i = 1; i <= n; ++i){
        Interval f[5005];
        int cnt = 0;
        for (int j = 0; j < k; ++j){
            if (abs(fish[j].x - i) > fish[j].r) continue;
            int dy = trunc(sqrt(fish[j].r * fish[j].r - (i - fish[j].x) * (i - fish[j].x)));
            f[cnt].l = max(1, fish[j].y - dy);
            f[cnt].r = min(m, fish[j].y + dy);
            ++cnt;
        }
        if (cnt == 0) continue;
        sort(f, f + cnt, comp);
        int nowl = f[0].l, nowr = f[0].r;
        for (int j = 1; j < cnt; ++j){
            if (nowl <= f[j].l && f[j].l <= nowr){
                if (nowr < f[j].r) nowr = f[j].r;
            }
            else{
                ans += nowr - nowl + 1;
                nowl = f[j].l;
                nowr = f[j].r;
            }
        }
        ans += nowr - nowl + 1;
    }
    cout << ans << endl;
    return 0;
}