学生选最近检查点：曼哈顿距离算法实现

在一个二维平面上有 N 个学生和 M 个检查点。第 i (1<=i<=n)个学生的的位置在(ai,bi)，第 j (1<=j<=m) 个检查点的位置在 (cj,dj) 。\n\n当老师给出信号后，每个学生都会跑向离他最近的检查点。在这里，我们用曼哈顿距离来定义学生距离与检查点的距离。\n曼哈顿距离的定义是：点 (x1,y1) 和 (x2,y2) 的曼哈顿距离等于 ∣x1−x2∣+∣y1−y2∣。其中，∣x∣ 表示 x 的绝对值。\n\n如果有多个检查点离某个学生距离相等，他/她会选择编号最小的那个。请聪明的你算算，每个学生分别会选择跑向哪个检查点。\n\n用C++做内容：首先，我们需要计算每个学生和每个检查点之间的曼哈顿距离。然后，对于每个学生，我们找到距离最小的检查点，并记录其编号。\n\n以下是一个可能的实现：\n\ncpp\n#include <iostream>\n#include <vector>\n#include <algorithm>\n#include <cmath>\n\nusing namespace std;\n\nstruct Student {\n int x, y; // 学生的位置\n int closestCheckpoint; // 最近的检查点编号\n int minDistance; // 最小距离\n};\n\nstruct Checkpoint {\n int x, y; // 检查点的位置\n int number; // 检查点编号\n};\n\nint main() {\n int n, m; // 学生数量和检查点数量\n cin >> n >> m;\n \n vector<Student> students(n);\n vector<Checkpoint> checkpoints(m);\n \n // 读取学生的位置\n for (int i = 0; i < n; i++) {\n cin >> students[i].x >> students[i].y;\n }\n \n // 读取检查点的位置和编号\n for (int i = 0; i < m; i++) {\n cin >> checkpoints[i].x >> checkpoints[i].y;\n checkpoints[i].number = i + 1;\n }\n \n // 计算每个学生和每个检查点之间的曼哈顿距离\n for (int i = 0; i < n; i++) {\n students[i].minDistance = abs(students[i].x - checkpoints[0].x) + abs(students[i].y - checkpoints[0].y);\n students[i].closestCheckpoint = checkpoints[0].number;\n \n for (int j = 1; j < m; j++) {\n int distance = abs(students[i].x - checkpoints[j].x) + abs(students[i].y - checkpoints[j].y);\n if (distance < students[i].minDistance) {\n students[i].minDistance = distance;\n students[i].closestCheckpoint = checkpoints[j].number;\n } else if (distance == students[i].minDistance && checkpoints[j].number < students[i].closestCheckpoint) {\n students[i].closestCheckpoint = checkpoints[j].number;\n }\n }\n }\n \n // 输出每个学生选择的检查点编号\n for (int i = 0; i < n; i++) {\n cout << students[i].closestCheckpoint << endl;\n }\n \n return 0;\n}\n\n\n该程序首先读取学生数量和检查点数量。然后，它依次读取学生和检查点的位置，并计算每个学生和每个检查点之间的曼哈顿距离。最后，它输出每个学生选择的检查点编号。\n\n希望能帮到你！