# D. For the Champion [문제 링크](https://codeforces.com/contest/2136/problem/D) ## Problem Statement *This is an interactive problem.* The RiOI team is hosting a robot championship! This time, your robot is teleported into an **infinite** 2D plane with the Cartesian coordinate system on it. There are \$n\$ anchor points on the plane, and the coordinates of the \$i\$-th anchor point are \$(x\_i, y\_i)\$ (\$-10^9 \le x\_i, y\_i \le 10^9\$). These are given to your robot by the jury as soon as it is teleported into the plane. However, your robot doesn't know its initial coordinates at first. To test the IQ of your robot, the RiOI team has come up with an interesting game. Your robot needs to find out the initial coordinates \$(X, Y)\$ (\$-10^9 \le X, Y \le 10^9\$) by making the following moves. In one move, assuming that its current coordinates are \$(a, b)\$, your robot can choose a non-negative integer \$k\$ (\$0 \le k \le 10^9\$) and do **one** of the following four operations: * Move up by \$k\$ units: \$(a, b + k)\$ * Move down by \$k\$ units: \$(a, b - k)\$ * Move left by \$k\$ units: \$(a - k, b)\$ * Move right by \$k\$ units: \$(a + k, b)\$ After each move, the jury gives the **minimum Manhattan distance** between the current coordinates of your robot and any anchor point. More formally, if the coordinates after the move are \$(c, d)\$, the jury outputs $$ \min_{1 \le i \le n}\big(|x_i - c| + |y_i - d|\big). $$ You must find the **initial** coordinates \$(X, Y)\$ in **no more than 10 moves**. ## Input Each test contains multiple test cases. The first line contains the number of test cases \$t\$ (\$1 \le t \le 100\$). For each test case: * The first line contains an integer \$n\$ (\$1 \le n \le 100\$) — the number of anchor points. * Then follow \$n\$ lines, the \$i\$-th line contains two integers \$x\_i\$ and \$y\_i\$ (\$-10^9 \le x\_i, y\_i \le 10^9\$) — the coordinates of the \$i\$-th anchor point. * The coordinates of the anchor points are pairwise distinct. ## Interaction For each test case, first read \$n\$ and all anchor points. Then you may make up to **10 moves**. To make a move, print one of the following lines: * `? U k` — move up by \$k\$ units * `? D k` — move down by \$k\$ units * `? L k` — move left by \$k\$ units * `? R k` — move right by \$k\$ units You must guarantee \$0 \le k \le 10^9\$. After each move, the jury prints an integer \$s\$ — the minimum Manhattan distance between the current robot position and any anchor point. To report that you found the initial coordinates, print: * `! X Y` — meaning the initial coordinates are \$(X, Y)\$. Printing the answer **does not** count as one of the 10 moves. Assume that the initial coordinates are \$(X, Y)\$, with \$-10^9 \le X, Y \le 10^9\$. After printing each query, **don’t forget to end the line and flush** the output. Otherwise, you will get the verdict `Idleness limit exceeded`. If at any interaction step you read `-1` instead of valid data, your solution must **exit immediately** (this means `Wrong answer` due to an invalid query or other mistake). The interactor in this problem is **not adaptive**: the initial coordinates of the robot do not change during the interaction. ## Hacks To perform a hack, use the following input format: * First line: an integer \$t\$ (\$1 \le t \le 100\$) — number of test cases. * For each test case: * One line with an integer \$n\$ (\$1 \le n \le 100\$); * \$n\$ lines with \$x\_i\$ and \$y\_i\$ (\$-10^9 \le x\_i, y\_i \le 10^9\$); * One final line with two integers \$X\$ and \$Y\$ (\$-10^9 \le X, Y \le 10^9\$) — the initial coordinates of the robot. **Flush tips** * C++: `fflush(stdout);` or `cout.flush();` * Python: `sys.stdout.flush()` ## 풀이 평면 왼쪽 위를 넘어서 왼쪽 위에서 가장 가까운 앵커, 평면 오른쪽 위를 넘어서 오른쪽 위에서 가장 가까운 앵커, 두 지점을 이용해 이차방정식을 풀었다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll MAX = 1e9; struct pos { int x, y; }; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n; cin >> n; pos p1 = {MAX, -MAX}; // (-10억, 10억)에서 가장 가까운 좌표 (a, b) pos p2 = {-MAX, -MAX}; // (10억, 10억)에서 가장 가까운 좌표 (c, d) for(int i=0;i<n;i++) { pos p; cin >> p.x >> p.y; if(abs(-MAX-p1.x) + abs(MAX-p1.y) > abs(-MAX-p.x) + abs(MAX-p.y)) p1=p; if(abs(MAX-p2.x) + abs(MAX-p2.y) > abs(MAX-p.x) + abs(MAX-p.y)) p2=p; } // 20억+a-x + 20억-b+y = 왼쪽 위 거리 (dist1) long long dist1; for(int i=0;i<2;i++) { cout << "? L " << MAX << '\n' << flush; cin >> dist1; } for(int i=0;i<2;i++) { cout << "? U " << MAX << '\n' << flush; cin >> dist1; } // 20억-c+x + 20억-d+y = 오른쪽 위 거리 (dist2) long long dist2; for(int i=0;i<4;i++) { cout << "? R " << MAX << '\n' << flush; cin >> dist2; } // x-y = 40억 + a - b - dist1 // -x-y = 40억 - c - d - dist2 cout << "! " << (p1.x-p1.y-dist1+p2.x+p2.y+dist2)/2 << ' ' << (8*MAX+p1.x-p1.y-dist1-p2.x-p2.y-dist2)/(-2) << '\n' << flush; } } ```