← 返回题目列表

Codeforces · 1184/C3

C3. 海蒂和图灵测试(难)

中文机器翻译题面 查看原题

网络人再次智胜戴立克!不幸的是,这次戴立克夫妇决定完全放弃这些任务,这意味着博士必须处理他们。

博士可以独自对付戴立克人,但海蒂现在必须确保网络人忙于下一项任务。

飞机上有 $$$k$$$ 戒指。对于每个环,$$$n$$$ 个点使用小的随机噪声进行均匀采样。任务是仅在给定噪声样本的情况下恢复环。

环和样本的生成方式如下。环的中心从以原点为中心、半径为$$$1\,000\,000$$$的圆盘中均匀采样,环的半径从$$$[250\,000, 750\,000]$$$中均匀采样。令 $$$R$$$ 为中心为 $$$(x, y)$$$ 且半径为 $$$r$$$ 的环。要从$$$R$$$采样点,角度$$$\theta$$$从$$$[0, 2\pi]$$$均匀采样,距离$$$d$$$从$$$[0.9r, 1.1r]$$$均匀采样。然后采样点的坐标 $$$(x+d\cos(\theta), y+d\sin(\theta))$$$ 四舍五入到最接近的整数。

环之间的距离是通过它们的豪斯多夫距离来测量的。在我们的例子中,两个环 $$$R_1, R_2$$$ 之间的距离可以写如下。设 $$$d$$$ 为两个中心之间的距离,$$$r_1, r_2$$$ 为半径。则距离为 $$$$$$dist(R_1, R_2)=\max(\min(d_{--}, d_{-+}),\min(d_{+-}, d_{++}), \min(d_{--}, d_{+-}), \min(d_{-+}, d_{++}))$$$$$$,其中$$$d_{++}=|d+r_1+r_2|$$$、$$$d_{+-}=|d+r_1-r_2|$$$、$$$d_{-+}=|d-r_1+r_2|$$$、$$$d_{--}=|d-r_1-r_2|$$$。

如果输出中的环 $$$R$$$ 与 $$$R_0$$$ 的豪斯多夫距离小于 $$$100\,000$$$,则我们说恢复了环 $$$R_0$$$。

如果所有环都恢复,则接受输出。保证任意两个环之间的距离大于$$$600\,000$$$。

请记住,人类可以非常轻松地解决此任务,因此请确保没有人类叛徒帮助网络人完成此任务。

输入

第一行包含一个整数 $$$k$$$ ($$$1 \leq k \leq 4$$$),即环的数量。

第二行包含一个整数 $$$n$$$ ($$$100 \leq n \leq 1\,000$$$),每个环的样本数。

以下 $$$n \times k$$$ 行包含样本,每行一个样本。

每行包含一对整数 $$$x_i, y_i$$$,其中 $$$(x_i, y_i)$$$ 是第 $$$i$$$ 个样本的坐标。

输出

打印 $$$k$$$ 行,每行描述一个环。

对于每一行,打印三个实数 $$$x_i, y_i, r_i$$$,其中 $$$(x_i, y_i)$$$ 和 $$$r_i$$$ 是第 $$$i$$$ 个环的坐标和半径。

环的顺序并不重要。

注意

以下是 $$$k=4$$$ 和 $$$n=100$$$ 的测试之一的样子。

您可以在此处下载示例输入和输出。