问题陈述
通灵者高桥发现了一张藏宝图。 到地图上有 50 在无人居住的岛屿的地下埋藏着宝藏。 该岛呈圆形,半径为 R=10^9。 不幸的是,地图上没有标明埋藏宝藏的位置。 既然不可能把地面全部挖出来,他决定用神通按照以下方式寻找宝藏。
- 选择所需位置并立一根木杆。
- 如果半径范围内有宝藏 D=10^6 从选定的位置开始,棍子将保持站立状态,他可以通过挖掘半径内的所有区域来找到宝藏 D.
- 如果半径范围内没有宝藏 D 从选定的位置开始,棒子会根据下面描述的规则向某个方向落下,从而提供宝藏位置的线索。
通过重复此过程直至 1000 次,尽快找到尽可能多的宝藏。
杆下落方向的规律
让 q=(qx, qy) 是杆所在的坐标,然后是下落方向 \theta (0\leq \theta<2\pi) 使用常数计算如下 \sigma 作为输入给出。
- 在尚未挖出的宝藏中,以与欧氏距离平方的倒数成正比的概率选择一个 q.
- 让 p=(px,py) 为所选宝藏的坐标,并计算方向 \hat{\theta}=\mathrm{atan2}(py-qy,px-qx) of p-q.
- 从具有均值的高斯分布中采样一个值 \hat{\theta} 和标准差 \sigma 并让 \theta 为余数除以 2\pi.
输入和输出
一、标准差 \sigma 在标准输入的一行中给出。 \sigma 是的倍数 0.001 并满足 0.001\leq \sigma\leq 0.100.
读取输入后,重复以下过程直至 1000 次。 在 k第进程,首先选择位置 (qx_k, qy_k) 站立杆,并按以下格式将单行输出到标准输出。
qx_k qy_k
qx_k 和 qy_k 必须是满足以下条件的整数 qx_k^2+qy_k^2\leq R^2。 如果您指定范围之外的点,您将得到 WA。 输出后面必须有一个新行,并且您必须刷新标准输出。 否则,提交的内容可能会被判定为 TLE.
然后,有关杆所发生情况的信息将在标准输入的一行中给出,如下所示。
如果杆朝以下方向落下 \theta_k:
0 \theta_k
\theta_k 介于 0 和 2\pi 并四舍五入为 10 小数位。
如果杆保持站立并且你在坐标处找到宝藏 (x_k,y_k):
r_k x_k y_k
r_k is 2 如果找到的宝藏是最后一个,并且 1 否则。
不同宝藏之间的距离保证大于 2D,所以你不会同时找到多个宝藏。
当你找到所有宝藏后,你必须立即终止程序。
否则,任何后续查询都不会返回响应,因此提交可能会被判断为 TLE or RE.
示例
| k | 输出 | 输入 |
|---|---|---|
| 0 | 0.051 |
|
| 1 | -449800796 341903569 |
0 4.2119508044 |
| 2 | -302629026 250885846 |
0 4.7012310463 |
| 3 | -132900000 -988000000 |
1 -132899921 -988157302 |
| \vdots |
评分
如果你没能找到里面的所有宝藏 1000 查询,测试用例的分数为 100F,其中 F 是您找到的宝藏数量。 如果你找到了所有的宝藏 Q(\leq 1000) 查询,测试用例的分数为 10000-5Q。 如果您还没有找到所有宝藏且查询次数小于 1000,提交的作品将被判定为 WA.
有200个测试用例,提交的分数是每个测试用例的总分。如果您得到的结果不是 AC 对于一个或多个测试用例,提交的分数将为零。比赛时间内获得的最高分将决定最终排名,比赛结束后不进行系统测试。如果超过一名参赛者获得相同分数,则排名将根据获得该分数的提交作品的提交时间来确定。
输入生成
让 \mathrm{rand}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。 \sigma 是由生成的 0.001\times \mathrm{rand}(1,100)。 坐标 p_0\cdots,p_{49} of 50 埋藏宝藏的生成方式如下。
- 生成坐标 p_i=(px_i,py_i) 的 i- 第一个埋藏的宝藏在满足条件的整数中均匀随机 px_i^2+py_i^2\leq R^2.
- 虽然已经生成了 p_j (j<i) 的欧几里得距离 p_i 小于或等于 2D,重新生成 p_i.
工具(输入生成器、可视化工具和本地测试器)
- 网页版:您可以观看动画并手动播放。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。
工具使用的输入/输出文件规范
提供给本地测试器的输入文件具有以下格式。
\sigma
px_0 py_0
\vdots
px_{49} py_{49}
\mathrm{seed}
最后 \mathrm{seed} 是用于生成下降方向的随机种子值。 由于方向取决于杆的位置,因此输入文件仅包含随机种子值。
本地测试器将程序的输出直接写入输出文件。您的程序可能会输出以以下内容开头的注释行 #。
可视化工具显示带有相应查询的注释行,这对于调试和分析可能很有用。
由于判断程序会忽略所有注释行,因此您可以提交按原样输出注释行的程序。
以下开头的注释行在可视化工具中具有特殊含义。
#r:当您不使用提供的本地测试器时,通过以以下形式输出给解决方案程序的响应字符串#r 0 0.0123456789,您可以向可视化工具提供信息。提供的本地测试器也会自动插入这些注释行。#c:通过按以下格式输出,可以标记一个点 (x, y) RGB 颜色 (r,g,b) (0\leq r,g,b\leq 255)。例如,您可以利用此功能来检查埋藏宝藏的可能位置。标记每回合都会被删除,因此如有必要,每回合都将其输出。
#c x y r g b