自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:14:21，当前版本为作者最后更新于2022-11-27 13:27:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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 即为最终答案。

视频题解

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