题目详解

问题重述

我们需要在最多 $10$ 次操作内，通过每次操作后得到的“当前点到最近锚点的曼哈顿距离”这一信息，反推出机器人的初始坐标 $(X, Y)$。

设 $V = 10^9$，保证 $-V \le X, Y \le V$。

---

核心思想

曼哈顿距离与 $45^\circ$ 旋转后的切比雪夫距离之间存在经典变换。定义：

$$u = x + y, \quad v = x - y$$

则原坐标系中的曼哈顿距离可表示为：

$$|x_i - X| + |y_i - Y| = \max(|u_i - U|, |v_i - V|) $$

其中 $U = X + Y$，$V = X - Y$。

因此，原问题转化为：在 $(u, v)$ 坐标系下，有 $n$ 个点 $(u_i, v_i)$，机器人初始位置为 $(U, V)$，每次移动后得到的是当前点与所有锚点之间的切比雪夫距离最小值。

---

操作在 $(u, v)$ 坐标系中的对应

在原始坐标系中的四种移动，对应到 $(u, v)$ 坐标系的变化如下：

原始操作	$(X, Y)$ 变化	$(U, V)$ 变化
右移 $k$	$(+k, 0)$	$(+k, +k)$
左移 $k$	$(-k, 0)$	$(-k, -k)$
上移 $k$	$(0, +k)$	$(+k, -k)$
下移 $k$	$(0, -k)$	$(-k, +k)$

可见，在 $(u, v)$ 坐标系中，我们无法独立调整 $U$ 和 $V$，但可以控制它们的和与差。

---

获取 $U = X + Y$

考虑执行以下四次操作：

1. 左移 $V$ 单位
2. 左移 $V$ 单位
3. 下移 $V$ 单位
4. 下移 $V$ 单位

设初始坐标为 $(X, Y)$，经过这四次操作后，机器人位置变为：

$$X' = X - 2V, \quad Y' = Y - 2V$$

由于 $-V \le X, Y \le V$，有 $X' \le -V$，$Y' \le -V$。

此时对于任意锚点 $(x_i, y_i)$，由于 $x_i \ge -V \ge X'$，$y_i \ge -V \ge Y'$，所以：

$$|x_i - X'| + |y_i - Y'| = (x_i - X') + (y_i - Y') = (x_i + y_i) - (X' + Y') $$

因此，评审团返回的距离为：

$$\begin{aligned} \text{res}_1 &= \min_{1 \le i \le n} \left( (x_i + y_i) - (X' + Y') \right) \\ &= \min_{1 \le i \le n} (x_i + y_i) - (X' + Y') \end{aligned} $$

而 $X' + Y' = (X - 2V) + (Y - 2V) = X + Y - 4V$，代入得：

$$\text{res}_1 = \min_{1 \le i \le n} (x_i + y_i) - (X + Y) + 4V $$

记 $S_{\min} = \min_{1 \le i \le n} (x_i + y_i)$，则：

$$X + Y = S_{\min} + 4V - \text{res}_1$$

---

获取 $V = X - Y$

考虑执行以下四次操作：

1. 左移 $V$ 单位
2. 左移 $V$ 单位
3. 上移 $V$ 单位
4. 上移 $V$ 单位

经过这四次操作后，机器人位置变为：

$$X' = X - 2V, \quad Y' = Y + 2V$$

此时 $X' \le -V$，$Y' \ge V$。

对于任意锚点 $(x_i, y_i)$，有 $X' \le -V \le x_i$

实际上，我们需要保证机器人位于所有锚点的左上方，即 $X' \le x_i$ 且 $Y' \ge y_i$ 对所有 $i$ 成立。

由于 $x_i \ge -V$，而 $X' \le -V$，所以 $X' \le x_i$ 成立。
由于 $y_i \le V$，而 $Y' \ge V$，所以 $Y' \ge y_i$ 成立。

因此，此时对于任意锚点，有 $X' \le x_i$ 且 $Y' \ge y_i$，所以：

$$|x_i - X'| + |y_i - Y'| = (x_i - X') + (Y' - y_i) = (Y' - X') + (x_i - y_i) $$

于是评审团返回的距离为：

$$\begin{aligned} \text{res}_2 &= \min_{1 \le i \le n} \left( (Y' - X') + (x_i - y_i) \right) \\ &= (Y' - X') + \min_{1 \le i \le n} (x_i - y_i) \end{aligned} $$

计算 $Y' - X' = (Y + 2V) - (X - 2V) = Y - X + 4V = -(X - Y) + 4V$。

记 $D_{\min} = \min_{1 \le i \le n} (x_i - y_i)$，则：

$$\text{res}_2 = -(X - Y) + 4V + D_{\min}$$

因此：

$$X - Y = 4V + D_{\min} - \text{res}_2$$

---

另一种对称做法（与标程一致）

标程中采用的是另一种对称的操作序列来获取 $X - Y$：

执行以下四次操作：

1. 右移 $V$ 单位
2. 右移 $V$ 单位
3. 上移 $V$ 单位
4. 上移 $V$ 单位

经过这四次操作后，机器人位置变为：

$$X' = X + 2V, \quad Y' = Y + 2V$$

此时 $X' \ge V$，$Y' \ge V$，机器人位于所有锚点的右上方。

对于任意锚点 $(x_i, y_i)$，有 $X' \ge x_i$，$Y' \ge y_i$，所以：

$$|x_i - X'| + |y_i - Y'| = (X' - x_i) + (Y' - y_i) = (X' + Y') - (x_i + y_i) $$

于是：

$$\begin{aligned} \text{res}_2 &= \min_{1 \le i \le n} \left( (X' + Y') - (x_i + y_i) \right) \\ &= (X' + Y') - \max_{1 \le i \le n} (x_i + y_i) \end{aligned} $$

而 $X' + Y' = (X + 2V) + (Y + 2V) = X + Y + 4V$，所以：

$$\text{res}_2 = X + Y + 4V - \max_{1 \le i \le n} (x_i + y_i) $$

这给出的是 $X + Y$ 的另一个表达式，而不是 $X - Y$。因此标程实际使用了不同的操作序列来获取 $X - Y$。

---

正确方案：获取 $X - Y$ 的另一种方法

执行以下四次操作：

1. 右移 $V$ 单位
2. 右移 $V$ 单位
3. 下移 $V$ 单位
4. 下移 $V$ 单位

经过这四次操作后，机器人位置变为：

$$X' = X + 2V, \quad Y' = Y - 2V$$

此时 $X' \ge V$，$Y' \le -V$，机器人位于所有锚点的右下方。

对于任意锚点 $(x_i, y_i)$，有 $X' \ge x_i$，$Y' \le y_i$，所以：

$$|x_i - X'| + |y_i - Y'| = (X' - x_i) + (y_i - Y') = (X' - Y') - (x_i - y_i) $$

于是：

$$\begin{aligned} \text{res}_2 &= \min_{1 \le i \le n} \left( (X' - Y') - (x_i - y_i) \right) \\ &= (X' - Y') - \max_{1 \le i \le n} (x_i - y_i) \end{aligned} $$

计算 $X' - Y' = (X + 2V) - (Y - 2V) = X - Y + 4V$。

记 $D_{\max} = \max_{1 \le i \le n} (x_i - y_i)$，则：

$$\text{res}_2 = (X - Y) + 4V - D_{\max}$$

因此：

$$X - Y = D_{\max} - 4V + \text{res}_2$$

---

最终方案

操作序列

第一步：获取 $X + Y$

执行四次操作：两次左移 $V$，两次下移 $V$。

得到返回值 $\text{res}_1$，计算：

$$X + Y = \min_{1 \le i \le n} (x_i + y_i) + 4V - \text{res}_1 $$

第二步：获取 $X - Y$

执行四次操作：两次右移 $V$，两次下移 $V$。

得到返回值 $\text{res}_2$，计算：

$$X - Y = \max_{1 \le i \le n} (x_i - y_i) - 4V + \text{res}_2 $$

解出初始坐标

$$X = \frac{(X + Y) + (X - Y)}{2}, \quad Y = \frac{(X + Y) - (X - Y)}{2} $$

总共使用 $8$ 次操作，满足 $\le 10$ 的限制。

---

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll V = 1000000000;

void solve() {
    int n;
    cin >> n;
    
    ll sum_min = LLONG_MAX;   // min(x_i + y_i)
    ll diff_max = LLONG_MIN;  // max(x_i - y_i)
    
    for (int i = 0; i < n; i++) {
        ll x, y;
        cin >> x >> y;
        sum_min = min(sum_min, x + y);
        diff_max = max(diff_max, x - y);
    }
    
    ll res1, res2;
    
    // 四次操作：两次左移 V，两次下移 V，得到 X+Y
    cout << "? L " << V << endl;
    cin >> res1;
    cout << "? L " << V << endl;
    cin >> res1;
    cout << "? D " << V << endl;
    cin >> res1;
    cout << "? D " << V << endl;
    cin >> res1;
    ll sum_ans = sum_min + 4 * V - res1;
    
    // 四次操作：两次右移 V，两次下移 V，得到 X-Y
    cout << "? R " << V << endl;
    cin >> res2;
    cout << "? R " << V << endl;
    cin >> res2;
    cout << "? D " << V << endl;
    cin >> res2;
    cout << "? D " << V << endl;
    cin >> res2;
    ll diff_ans = diff_max - 4 * V + res2;
    
    ll X = (sum_ans + diff_ans) / 2;
    ll Y = (sum_ans - diff_ans) / 2;
    
    cout << "! " << X << " " << Y << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    
    return 0;
}

---

正确性验证

推导 $X + Y$

机器人经过两次左移 $V$ 和两次下移 $V$ 后，位置为 $(X - 2V, Y - 2V)$。由于 $X, Y \ge -V$，有 $X - 2V \le -V$，$Y - 2V \le -V$。对所有锚点 $(x_i, y_i)$，$x_i \ge -V$，$y_i \ge -V$，因此 $X - 2V \le x_i$，$Y - 2V \le y_i$。

曼哈顿距离：

$$|x_i - (X - 2V)| + |y_i - (Y - 2V)| = (x_i - X + 2V) + (y_i - Y + 2V) = (x_i + y_i) - (X + Y) + 4V $$

取最小值：

$$\text{res}_1 = \min_i (x_i + y_i) - (X + Y) + 4V$$ $$\Rightarrow X + Y = \min_i (x_i + y_i) + 4V - \text{res}_1 $$

推导 $X - Y$

机器人经过两次右移 $V$ 和两次下移 $V$ 后，位置为 $(X + 2V, Y - 2V)$。由于 $X, Y \le V$，有 $X + 2V \ge V$，$Y - 2V \le -V$。对所有锚点 $(x_i, y_i)$，$x_i \le V$，$y_i \ge -V$，因此 $X + 2V \ge x_i$，$Y - 2V \le y_i$。

曼哈顿距离：

$$|x_i - (X + 2V)| + |y_i - (Y - 2V)| = (X + 2V - x_i) + (y_i - Y + 2V) = (X - Y) + 4V - (x_i - y_i) $$

取最小值：

$$\text{res}_2 = \min_i \left( (X - Y) + 4V - (x_i - y_i) \right) = (X - Y) + 4V - \max_i (x_i - y_i) $$$$\Rightarrow X - Y = \max_i (x_i - y_i) - 4V + \text{res}_2 $$

推导完毕。