QOJ.ac

QOJ

时间限制: 2.0 s 内存限制: 256 MB 总分: 100

#12912. Mond

统计

你是月球探险队的一员,目前正在绕月轨道上为着陆做准备。最佳着陆点已经经过精确计算,并且此前已向该点派遣了一个信标来引导你的着陆。然而,事实证明该信标信号太弱,无法到达轨道——更准确地说,只有当接收者位于距离信标 1 公里的球体内时,才能接收到信号;这意味着如果接收者在月球表面,则必须位于以信标为圆心、半径为 1 公里的圆内。

你已经确定了信标可能存在的区域,即陨石坑侧面一个 $100$ 公里 $\times$ $100$ 公里的正方形区域,但它可能位于该正方形内的任何位置。你确定信标精确位置的唯一方法是向月球表面发送无人月球着陆器,尝试捕捉其信号。

每个月球着陆器都没有与轨道的实时链路,必须预先编程。其程序是一系列月球表面的航点,着陆器在航点之间沿直线移动。由于陨石坑非常陡峭,着陆器永远不能减小其 $x$ 坐标。换句话说,连续航点的 $x$ 坐标必须是非递减的(可以相等),第一个航点的 $x$ 坐标必须等于 $0$(陨石坑高处),最后一个航点的 $x$ 坐标必须等于 $100$(陨石坑低处)。航点的 $y$ 坐标可以是 $0$ 到 $100$ 之间的任意数值。坐标单位为公里。

在航点之间移动时,月球着陆器会监听信标。如果在任何时刻着陆器距离信标在 1 公里以内,它就会记录下这一事实。在整个行程结束后,月球着陆器会向轨道传输一个比特的信息:在沿途的任何一点,它是否曾处于距离信标 1 公里的范围内?

这个比特仍然无法让你很好地确定信标的位置。然而,通过发送多个带有不同程序的月球着陆器,你实际上可以非常精确地确定信标的位置。你需要这样做。你可以根据之前月球着陆器传输的结果来制定每个月球着陆器的程序。

你最多可以发送 60 个月球着陆器,并且需要确定信标的位置,误差不超过一毫米($10^{-6}$ 公里)。

交互

最初,你的程序不应从标准输入读取任何内容。

为了发送一个月球着陆器,你的程序应打印其路线。路线以航点数量 $n$ 开头($n$ 不得超过 250),随后是 $n$ 对浮点数:航点的 $x$ 和 $y$ 坐标。所有坐标必须在 $0$ 到 $100$ 之间(含边界),第一个 $x$ 坐标必须恰好为 $0$,最后一个 $x$ 坐标必须恰好为 $100$,且 $x$ 坐标必须是非递减的。这些条件将在没有额外容差的情况下进行检查。航点重合是允许的。打印路线后,请务必刷新标准输出。

然后,你可以从标准输入读取月球着陆器的行程结果,为一个整数:如果着陆器在行程中从未进入距离信标 1 公里的范围内,则为 0;如果进入过,则为 1。交互器将使用至少双精度浮点数来进行此比较,并且在比较时不会有任何额外的容差,因此如果着陆器恰好经过距离信标 1 公里的位置,你的程序可能会收到两种结果中的任意一种。

当你足够精确地确定了信标的位置后,你应该输出数字 0,后跟两个浮点数:你对信标位置的猜测。如果两个坐标都在 $0$ 到 $100$ 之间(含边界),且该位置与信标实际位置之间的距离不超过 $10^{-6}$ 公里,你的解将被接受。此比较也将使用至少双精度浮点数进行,且同样没有任何额外容差。记住在输出猜测后刷新标准输出并优雅地终止程序。

你最多可以发送 60 个月球着陆器。

在样例中,信标位于样例输出所示的位置,但如果你的解发送了不超过 60 个月球着陆器,并输出了任何两个坐标都在 $0$ 到 $100$ 之间的位置,它就能通过样例。

本题共有 50 个非样例测试用例。每个用例中信标的两个坐标都是固定的,且是独立均匀随机生成的。

样例

输入 1

1
1

输出 1

2 0.0 45.0 100.0 46.0
6 0.0 0.0 12.0 0.0 12.0 50.0 57.0 57.0 70.0 30.0 100.0 90.0
0 12.34 45.67

说明

上图对应于样例输出中的第二个月球着陆器。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.