Public Judge

pjudge

Time Limit: 1 s Memory Limit: 256 MB Total points: 100 Interactive Hackable ✓

# 21616. 【PR #1】直线

Statistics

这是一道交互题

P 国的领土是边长为 $2\times 10^{12}$ 的正方形。我们以领土的中心为原点,平行于正方形的边建立平面直角坐标系,则整个 P 国领土的范围为 $[-10^{12},10^{12}]\times[-10^{12},10^{12}]$。

在 P 国的领土上有 $N$ 条直线 $y=a_ix+b_i$,其中 $a_i, b_i$ 均为 $[-10^4, 10^4]$ 内的整数。但是你并不知道 $a_i$ 与 $b_i$ 的值。为了得到这些信息,你可以向国王进行下述询问不超过 $Q_\text{max}$ 次:

  • 给出平面上一个点 $(x,y)$,国王告诉你 $(x,y)$ 到这 $N$ 条直线的距离之和。

你需要通过询问来复原出所有的 $N$ 条直线。

实现细节

你不需要,也不应该实现 main() 函数,或在任何文件与标准输入/输出流中读入或输出任何信息。

你只需要包含头文件 lines.h,并实现以下函数:

void solve(int subtask_id, int N);
  • 该函数会被恰好调用一次。
  • 参数 subtask_id 表示当前测试点的子任务编号。
  • 参数 N 即为题目描述中的 $N$,表示直线的数量。

你可以调用以下函数:

long double query(long double x, long double y);
  • 参数 xy 表示你所询问的点的坐标 $P(x, y)$。
  • 你需要保证 $x,y\in[-10^{12},10^{12}]$。
  • 该函数会返回点 $(x,y)$ 到这 $N$ 条直线的距离之和。
  • 在最终测试时,交互库保证该函数在调用时返回的结果与真实答案的绝对误差或相对误差不超过 $10^{-13}$,你至多能调用这个函数 $Q_\text{max}$ 次。
    • 即,设交互库返回的结果为 $x$,真实的答案为 $y$,则有 $\frac{|x-y|}{\max(1, y)} \leq 10^{-13}$。
void the_lines_are(std::vector<int> a, std::vector<int> b);
  • 你需要调用该函数恰好一次。
  • 你需要保证 a, b 均为长度恰好为 $N$ 的数组,其中对于每个 $0 \leq i < n$,a[i]b[i] 分别描述一条直线。
  • 你可以以任意的顺序返回这些直线。

样例交互库

在下发文件中,你可以找到样例交互库 grader_1.cppgrader_2.cpp。这两份交互库在除了回答询问的方式以外完全相同,你可以通过这两份交互库的实现来帮助你理解并实现这道题目。需要注意的是,在进行最终测试时,交互库的实现与这两种样例交互库均有所不同,因此你不应当依赖此交互库的实现。

样例交互库将通过以下格式在标准输入中读入数据:

  • 第一行,一个正整数,表示 $\texttt{subtask_id}$。
  • 第二行,三个正整数 $N,Q_\text{max},Q_\text{min}$。
  • 之后 $N$ 行,每行两个整数 $a_i,b_i$。

在交互完成后,交互库会将你的程序所返回的结果输出至标准输出。注意样例交互库不会检查你的答案是否正确,只会将你调用 the_lines_are 函数时传递的参数输出。

两种样例交互库的区别如下:

  • 对于第一份样例交互库 grader_1.cpp,样例交互库将在 query(x, y) 被调用时计算点 $(x, y)$ 到所有直线的距离。
  • 对于第二份样例交互库 grader_2.cpp,对于每组询问,样例交互库将会向标准输出流中输出一行 query(x, y) =,你需要在标准输入中输入该组询问的答案。

你可以在终端使用以下命令来编译你的程序:

g++ grader_1.cpp lines.cpp -o lines_1 -O2
g++ grader_2.cpp lines.cpp -o lines_2 -O2

在最终评测时,对于任何合法的(使用不超过 $Q_\text{max}$ 次询问操作)交互过程,保证交互库使用的时间不超过 $0.2$ 秒,使用的内存不超过 $2\text{ MiB}$。

样例

以下是一组可能的对样例交互库的输入。

1
1 10000 10000
1 0

以下是一次合法的交互过程。

交互库调用 选手程序调用 返回值
solve(1, 1) $ $ $ $
$ $ query(0, 0) $0$
$ $ query(1, 1) $0$
$ $ the_lines_are({1}, {0}) $ $

子任务

如果你在某个测试点中没有在时间限制($1.0$ 秒)与空间限制($256\text{ MiB}$)内返回结果,或发生了运行时错误,或最终返回的答案不正确,则你在该测试点的得分为 $0$。

否则,设 $Q$ 为你在该测试点中调用函数 query 的次数,$S$ 为该测试点的满分,则:

  • 若 $Q_\text{max} < Q$,则你的得分为 $0$。
  • 若 $Q_\text{min} < Q \leq Q_\text{max}$,则你的得分为 $S \cdot \left( 1 - 0.7 \cdot \dfrac{Q - Q_\text{min}}{Q_\text{max} - Q_\text{min}} \right)$。
  • 若 $Q \leq Q_\text{min}$,则你的得分为 $S$。

在一个子任务中,你所得到的分数即为所有测试点分数的最小值。

对于所有数据,$1 \leq N \leq 100$,$-10^4 \leq a_i,b_i \leq 10^4$,$Q_\text{max}=10^4$,任意两条直线均不互相平行。

子任务编号 $Q_\text{min} = $ 特殊性质 分值
$1$ $10^4$ $N = 1$ $11$
$2$ $N = 2$ $13$
$3$ $N = 3$ $7$
$4$ $402$ $-500 \leq a_i,b_i \leq 500$ $19$
$5$ $N \leq 30$ $23$
$6$ $ $ $27$

时间限制:$\texttt{1s}$

空间限制:$\texttt{256MB}$