闲聊
好久不见啊，终于放暑假了。这题好妙啊，写个题解吧。
题意
随机生成 $n$ 个点 $\left(x_i, y_i\right)$，你要用尽可能少的询问来找出这些点。坐标的绝对值不超过 $100$ 且任意两点之间的横纵坐标之差都大于等于 $1$。
每次询问给出 $a, b, c$，评测机按任意顺序返回这 $n$ 个点在直线 $ax + by + c = 0$ 上的投影（精度 $10^{-4}$）。你需要保证 $a, b, c$ 的绝对值均不超过 $100$ 且 $\lvert a \rvert + \lvert b \rvert \geq 0.1$。
$t$ 组数据。
$n \leq 25, t \leq 50$
题解
一条直线显然不可能找出。考虑用两条直线找点。仔细思考就会发现，两条直线虽然可以找到所有 $x$ 坐标 和 $y$ 坐标，但无法确定如何匹配起来。所以加入第 $3$ 条直线。
我们可以通过询问一条与 $x$ 轴平行的直线来确定所有点的 $x$ 坐标。再通过询问一条与 $y$ 轴平行的直线来确定所有点的 $y$ 坐标。现在我们要用第 $3$ 条直线把这些点匹配。我们可以询问一条斜率极小的直线，比如 $y = 0.001x$，带入每个点的 $x$ 坐标，算出一个大致的 $y$ 坐标，然后去匹配准确的 $y$ 坐标。因为任意两点之间的横纵坐标之差都大于等于 $1$，所以不会找错。
代码
// Please submit with C++17! It's best to use C++20 or higher version.
// By Koicy (https://koicy.ly)
// rbtree (i@koicy.ly)
// Drifting and struggling in the mist.
#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define _CONSOLE 0
// #define EFILE ""
using namespace std;
using tp = long long;
constexpr tp ZERO = 0, ONE = 1, INF32 = -1u >> 2, INF = -1ull >> 2;
template <typename _Type, size_t _Size>
struct mray : array<_Type, _Size + 9> {
_Type& operator[](size_t index) { return this->at(index); }
};
// Defines
// Constants
// Classes
// Typedeves
// Variables
tp n;
// Arrays
mray<double, 32> a, b;
mray<pair<double, double>, 32> c;
// Functions
void MIST() {
}
void STRUGGLING([[maybe_unused]] tp TEST_NUMBER) { // :/
cin >> n;
cout << "? 0 1 0" << endl;
for (tp i = 1; i <= n; ++i) cin >> a[i] >> a[0];
cout << "? 1 0 0" << endl;
for (tp i = 1; i <= n; ++i) cin >> b[0] >> b[i];
cout << "? -0.001 1 0" << endl;
for (tp i = 1; i <= n; ++i) cin >> c[i].first >> c[i].second;
stable_sort(a.begin() + 1, a.begin() + n + 1);
stable_sort(c.begin() + 1, c.begin() + n + 1);
cout << "! ";
for (tp i = 1; i <= n; ++i) {
double y = c[i].second + c[i].first * 1000 - a[i] * 1000, l = b[n];
for (tp j = 1; j < n; ++j) {
if (abs(y - b[j]) < abs(y - l)) l = b[j];
}
cout << a[i] << ' ' << l << ' ';
}
cout << endl;
}
#include <fstream>
signed main() {
tp t = 0, _t = 1;
ios::sync_with_stdio(0);
cin.tie(0);
#if !_CONSOLE
#ifdef _LOCAL
static ifstream _in("input.in");
cin.rdbuf(_in.rdbuf());
#else
#ifdef EFILE
static ifstream _in(EFILE ".in");
static ofstream _out(EFILE ".out");
cin.rdbuf(_in.rdbuf());
cout.rdbuf(_out.rdbuf());
#endif
#endif
#endif
cin >> _t;
MIST();
while (t < _t) STRUGGLING(++t);
return 0;
}
//*/Casual Chat
Long time no see! Finally, it's summer vacation. This problem is interesting. Let's write a solution for it.
Problem Statement
Randomly generate $n$ points $\left(x_i, y_i\right)$. You need to find these points using as few queries as possible. The coordinates are absolute values that do not exceed $100$, and the difference between any two points' x or y coordinates is greater than or equal to $1$.
Each query gives $a, b, c$, and the judging system returns the projection of these $n$ points on the line $ax + by + c = 0$ in any order (with precision $10^{-4}$). You need to ensure that the absolute values of $a, b, c$ are all less than or equal to $100$, and $\lvert a \rvert + \lvert b \rvert \geq 0.1$.
There are $t$ sets of data.
$n \leq 25, t \leq 50$
Solution
Using a single line is obviously impossible. Let's try using two lines to find the points. After careful consideration, we'll find that although two lines can determine all the x and y coordinates, they cannot uniquely match them. So let's add a third line.
We can determine all the x coordinates of the points by querying a line parallel to the x-axis. Then, we can determine all the y coordinates of the points by querying a line parallel to the y-axis. Now, we need to match these points using the third line. We can query a line with an extremely small slope, for example, $y = 0.001x$, and substitute each x coordinate of the points to obtain an approximate y coordinate. Then, we can match the exact y coordinate. Since the difference between any two points' x or y coordinates is greater than or equal to $1$, there won't be any mistakes.
Code
// Please submit with C++17! It's best to use C++20 or higher version.
// By Koicy (https://koicy.ly)
// rbtree (i@koicy.ly)
// Drifting and struggling in the mist.
#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define _CONSOLE 0
// #define EFILE ""
using namespace std;
using tp = long long;
constexpr tp ZERO = 0, ONE = 1, INF32 = -1u >> 2, INF = -1ull >> 2;
template <typename _Type, size_t _Size>
struct mray : array<_Type, _Size + 9> {
_Type& operator[](size_t index) { return this->at(index); }
};
// Defines
// Constants
// Classes
// Typedeves
// Variables
tp n;
// Arrays
mray<double, 32> a, b;
mray<pair<double, double>, 32> c;
// Functions
void MIST() {
}
void STRUGGLING([[maybe_unused]] tp TEST_NUMBER) { // :/
cin >> n;
cout << "? 0 1 0" << endl;
for (tp i = 1; i <= n; ++i) cin >> a[i] >> a[0];
cout << "? 1 0 0" << endl;
for (tp i = 1; i <= n; ++i) cin >> b[0] >> b[i];
cout << "? -0.001 1 0" << endl;
for (tp i = 1; i <= n; ++i) cin >> c[i].first >> c[i].second;
stable_sort(a.begin() + 1, a.begin() + n + 1);
stable_sort(c.begin() + 1, c.begin() + n + 1);
cout << "! ";
for (tp i = 1; i <= n; ++i) {
double y = c[i].second + c[i].first * 1000 - a[i] * 1000, l = b[n];
for (tp j = 1; j < n; ++j) {
if (abs(y - b[j]) < abs(y - l)) l = b[j];
}
cout << a[i] << ' ' << l << ' ';
}
cout << endl;
}
#include <fstream>
signed main() {
tp t = 0, _t = 1;
ios::sync_with_stdio(0);
cin.tie(0);
#if !_CONSOLE
#ifdef _LOCAL
static ifstream _in("input.in");
cin.rdbuf(_in.rdbuf());
#else
#ifdef EFILE
static ifstream _in(EFILE ".in");
static ofstream _out(EFILE ".out");
cin.rdbuf(_in.rdbuf());
cout.rdbuf(_out.rdbuf());
#endif
#endif
#endif
cin >> _t;
MIST();
while (t < _t) STRUGGLING(++t);
return 0;
}
//*/