注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "nice_lines.h"。

题目描述

题目译自 Romanian Master of Informatics 2020 Day2 T1 「Nice Lines」

海盗公主 Roxette 来到了雷米安群岛的秘密岛屿。据说那里埋藏着著名的宝藏——美丽的金线。

这个秘密岛屿是一个边长为 $2 \times 10^{12}$ 米的正方形。岛上的任何一点都可以用笛卡尔坐标系表示，其中 $(0,0)$ 位于中心，两条坐标轴与岛的边平行。

岛上埋藏着 $N$ 条美丽的金线。第 $i$ $(0 \leq i < N)$ 条金线由线性方程 $y = a_{i} x + b_{i}$ 表示的所有实数点 $(x, y)$ 组成。

Roxette 可以使用一种特殊设备，称为测线仪。给定岛上的任意一点 $p$，测线仪将计算该点到每条金线的距离之和。

不幸的是，测线仪的使用次数有限。你能帮助 Roxette 在有限的测线仪使用次数内找到所有的宝藏吗？

实现细节

你必须实现一个函数：

void solve(int N);

这个函数将在交互开始时被调用一次。$N$ 是岛上隐藏的金线数量。

这个函数可以调用另一个函数，但不能超过 $Q_{\max}$ 次：

long double query(long double x, long double y);

你只能用 $-10^{12} \leq x, y \leq 10^{12}$ 的参数调用这个函数。

它返回应用于笛卡尔坐标 $(x, y)$ 的测线仪的结果，即该点到每条金线的距离之和。注意，金线本身不会提供给你，因为你的目标是找到它们。

当你找到所有 $N$ 条金线时，必须调用以下函数：

void the_lines_are(std::vector<int> a, std::vector<int> b);

其中 $a[i]$ 和 $b[i]$ 表示第 $i$ $(0 \leq i < N)$ 条金线。你可以以任何顺序返回这些直线。

样例

交互器调用	程序调用
solve(1, 1, 1)	query(0, 0) 返回 0
	query(1, 1) 返回 0
	the_lines_are({1}, {0})

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 100$
• $-10000 \leq a_{i}, b_{i} \leq 10000$
• 没有两条直线是平行的

对于每个测试点，得分按以下步骤计算：

• 令 $Q$ 为 query 函数被调用的次数。
• 如果 $Q > Q_{\max}$，或者金线未正确报告，则测试点得分为 $0$。
• 如果 $Q \leq Q_{\min}$，则测试点得分为 $1$。
• 否则，测试点得分为 $1 - 0.7 \cdot \frac{Q - Q_{\min}}{Q_{\max} - Q_{\min}}$。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$11$	$N = 1$；$Q_{\min} = 10000, Q_{\max} = 10000$
$2$	$13$	$N = 2$；$Q_{\min} = 10000, Q_{\max} = 10000$
$3$	$7$	$N = 3$；$Q_{\min} = 10000, Q_{\max} = 10000$
$4$	$19$	$-500 \leq a_{i}, b_{i} \leq 500$；$Q_{\min} = 402, Q_{\max} = 10000$
$5$	$23$	$N \leq 30$；$Q_{\min} = 402, Q_{\max} = 10000$
$6$	$27$	$Q_{\min} = 402, Q_{\max} = 10000$