B3679 [语言月赛202211] Zone Selection 题解

· · 题解

B3679 [语言月赛202211] Zone Selection 题解

Source & Knowledge

2022 年 11 月语言月赛，由洛谷网校入门计划/基础计划提供。

本题考察对循环结构和分支结构的高级应用。

文字题解

题目大意

分别给定 n 个坐标 (x _ i, y _ i)，k 个坐标 (x _ i, y _ i)，T 个坐标 (x _ i, y _ i)，保证 k 个坐标在之前的 n 个坐标中出现过。

对第三组数据 T 个坐标中的每个坐标，求出第一组数据 n 个坐标中与之最近的坐标是否在第二组 k 个坐标中。

解析

按照题目给出的信息，写出计算距离的函数。

int getDist(int x, int y, int z, int w) {
    // 求出 (x, y) 与 (z, w) 之间的距离
    return sqrt((x - z) * (x - z) + (y - w) * (y - w));
}

首先录入第一组 n 个坐标，对于第二组 k 个坐标中的每个坐标，逐个判断其属于 n 个坐标中的哪一个即可。找到对应的坐标后，我们对其进行标记以便于后面的判断。

这里可以使用传统数组或者结构体或者其他方式解决，以下为使用结构体的例子：

#define MAXN 1005

struct Position {
    int x, y;
    bool isMarked;
} a[MAXN];

// 函数部分
for (int i = 1; i <= n; ++i) {
    cin >> a[i].x >> a[i].y;
}

for (int i = 1; i <= k; ++i) {
    int x, y;
    cin >> x >> y;
    for (int j = 1; j <= n; ++j)
        if (a[j].x == x && a[j].y == y) {
            a[j].isMarked = true;
            break;
        }
}

其次，录入 T 组询问坐标，对每个坐标，找到第一组 n 个坐标中与之最远的一个。

遍历过程中，我们可以记录当前的最大距离和最大距离对应的节点，如果现在的节点与当前节点距离大于之前的最大距离，那么记录这个节点，同时更新当前的最大距离。例子如下：

由于我们保证了当且仅当“大于”才更新，所以我们保证了当距离相同时取到了标号最小的。

for (int i = 1; i <= t; ++i) {
    int x, y;
    cin >> x >> y;
    double maxDist = -1;
    int ans = 0;
    for (int j = 1; j <= n; ++j) {
        if (getDist(x, y, a[j].x, a[j].y) > maxDist) {
            ans = j;
            maxDist = getDist(x, y, a[j].x, a[j].y);
        }
    }
    ...
}

此时 ans 变量存储的是最远的机器对应的数组下标，使用上面的 isMark 参数进行判断计数即可。

if (a[ans].flag) {
        ++res;
    }
}

res 即为最终答案。

视频题解

完整代码请在视频中查看。