华为软件类笔试-嵌入式软件开发 9-13

《嵌入式软件开发笔试与面试手册》：https://blog.nowcoder.net/zhuanlan/jvN8gj

《软件开发笔试汇总》：https://blog.nowcoder.net/zhuanlan/0oDWVm

第三题基站建设

运营商建设基站时需要关注很多因素，其中: 基站的信号覆盖范围、建设成本就是要考虑的部分因素。

以一个二维数组(10000* 10000) 表示需要服务的有效地域范围，假设个基站坐标为(2,2)，可覆盖的范围为基站为中心的3*3的矩阵(若不在有效地域范围则无效)。

现有多个基站候选点，我们需要决策在哪些地点建设基站，要求:在尽可能多地覆盖服务地域的前提下尽可能少地建设基站

输入

第一行为候选基站的坐标点个数n (0<n<10000)，后面的每一行都表示候选基站的行列位置，格式为: 行位置+空格+列位置

输出

格式为:建造的基站个数+空格+覆盖的地域面积

样例1

输入

4 2 2 5 5 5 4 5 3 1

输出

3 24

解释:

最佳的策略为选择(2,2)、(5,5)、(5,3)这三个基站候选点，他们的覆盖面积为24

#include <iostream>
#include <map>
#include <vector>

using namespace std;

struct Point {
    int x, y;
    Point(int _x, int _y) : x(_x), y(_y) {}
    bool operator<(const Point &other) const {
        return x < other.x || (x == other.x && y < other.y);
    }
};

bool isValid(int x, int y) {
    return x >= 0 && x < 10000 && y >= 0 && y < 10000;
}

int main() {
    int n;
    cin >> n;
    vector<Point> pos;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        pos.emplace_back(x, y);
    }

    map<Point, int> vis;
    int cnt = n;
    int square = 0;

    for (const auto &p : pos) {
        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) {
                Point np(p.x + dx, p.y + dy);
                if (!isValid(np.x, np.y)) continue;
                if (!vis[np]) square++;
                vis[np]++;
            }
        }
    }

    for (const auto &p : pos) {
        int covered = 0;
        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) {
                Point np(p.x + dx, p.y + dy);
                if (!isValid(np.x, np.y)) continue;
                if (vis[np] > 1) covered++;
            }
        }
        if (covered == 9) {
            cnt--;
            for (int dx = -1; dx <= 1; dx++) {
                for (int dy = -1; dy <= 1; dy++) {
                    Point np(p.x + dx, p.y + dy);
                    if (!isValid(np.x, np.y)) continue;