题目类型说明

这是一道提交函数题 / 库调用题。你需要实现函数 solve，并通过题目给定的 query 接口与评测程序交互。

你需要实现：

std::vector<std::pair<int, int>> solve(int B, int K, int W);

评测程序会提供：

std::vector<int> query(std::vector<std::pair<int, int>> probes);

题目描述

Petr 所在的机器人兴趣小组决定制造一架新一代无人机：它能够躲避敌方雷达，同时还能精确确定敌方地面目标的位置。

无人机配备了一台摄像机。摄像机扫描地面时，只能得到：

• 观测区域内一共有多少个敌方目标；
• 但不能直接得到这些目标的具体位置。

摄像机把地面看成一个整数坐标网格。共有 K 个敌方目标，第 i 个目标位于未知的整点坐标 (x_i, y_i) 上，并且满足：

• -B <= x_i, y_i <= B

其中整数 B 表示初始扫描区域的范围。

为了进一步确定这些目标的精确坐标，无人机会向地面发射探针。探针可以成批（成“群”）发射，一次可以发射多个。每个探针会飞向坐标 (s_j, t_j)，其中：

• 1 <= j <= D
• -10^8 <= s_j, t_j <= 10^8

这里 D 是这一批探针的数量。

当探针到达地面后，它会计算自己到每一个目标的曼哈顿距离，并把结果传回无人机。因此，一次包含 D 个探针的查询会返回一共 K \times D 个距离值：

对所有 i \in \{1, 2, \dots, K\} 和 j \in \{1, 2, \dots, D\} 都会出现。

但所有数据包会同时返回，因此你无法知道每个距离值到底来自哪个探针、对应哪个目标。

请帮助 Petr 和他的朋友们，编写程序 drone，在不超过 W 批探针的前提下，精确确定所有目标的坐标。

实现细节

你需要实现：

std::vector<std::pair<int, int>> solve(int B, int K, int W)

• B：扫描区域范围；
• K：敌方目标数；
• W：最多允许发送的探针批次数。

该函数只会被调用一次。你需要返回一个由若干对 (x_i, y_i) 组成的列表，表示所有目标坐标。返回顺序无关。

评测程序提供函数：

std::vector<int> query(std::vector<std::pair<int, int>> probes)

• probes：本次发射的探针目标坐标列表 (s_j, t_j)；
• 每个探针坐标都必须在区间 [-100000000, 100000000] 内。

每次调用 query 时，它会返回所有“目标 - 探针”配对的曼哈顿距离，但返回顺序是未指定的。

额外限制：

• 调用 query 的总次数不能超过 W；
• 所有批次中使用的探针总数不能超过 20000；
• 如果违反题面中的任一条件，程序会被终止，并像本地 grader 一样给出相应错误信息。

数据范围

• 1 <= B <= 10^8
• 1 <= K <= 20
• 2 <= W <= 10^4

子任务

只有通过该子任务及其依赖的所有子任务，才能获得该子任务的分数。

示例交互

说明

• 你返回的所有目标坐标都必须是整数坐标；
• 返回顺序不影响判定结果；
• 本题为库调用题，评测时你的代码会与 grader 一同编译执行，而不是通过标准输入输出完成交互。