CF1184C3.Heidi and the Turing Test (Hard)

The Cybermen have again outwitted the Daleks! Unfortunately, this time the Daleks decided to abandon these tasks altogether, which means the Doctor has to deal with them.

The Doctor can handle the Daleks on his own, but Heidi now has to make sure that the Cybermen are kept busy with this next task.

There are $k$ rings on a plane. For each ring, $n$ points are uniformly sampled with a small random noise. The task is to recover the rings given only the noisy samples.

The rings and the samples are generated as follows. The center of a ring is uniformly sampled from a disk of radius $1\,000\,000$ centered at the origin, and the radius of the ring is uniformly sampled from $[250\,000, 750\,000]$. Let $R$ be a ring with center $(x, y)$ and radius $r$. To sample a point from $R$, an angle $\theta$ is uniformly sampled from $[0, 2\pi]$ and a distance $d$ is uniformly sampled from $[0.9r, 1.1r]$. The coordinates of the sampled point are then $(x+d\cos(\theta), y+d\sin(\theta))$ rounded to the closest integers.

The distance between rings is measured by their Hausdorff distance. In our case, the distance between two rings $R_1, R_2$ can be written as follow. Let $d$ be the distance between the two centers and $r_1, r_2$ be the radii. Then the distance is $$dist(R_1, R_2)=\max(\min(d_{--}, d_{-+}),\min(d_{+-}, d_{}), \min(d_{--}, d_{+-}), \min(d_{-+}, d_{}))$$, where $d_{++}=|d+r_1+r_2|$, $d_{+-}=|d+r_1-r_2|$, $d_{-+}=|d-r_1+r_2|$, $d_{--}=|d-r_1-r_2|$.

We say that a ring $R_0$ is recovered if one of the rings $R$ in the output has Hausdorff distance less than $100\,000$ from $R_0$.

An output is accepted if all the rings are recovered. It is guaranteed that the distances between any two rings is greater than $600\,000$.

Remember that a human can very easily solve this task, so make sure that no human traitors are helping the Cybermen complete this task.

赛博人再次智胜了戴立克！不幸的是，这一次戴立克决定彻底放弃这些任务，这意味着博士必须独自应对他们。

博士可以独自应付戴立克，但海蒂现在必须确保赛博人被接下来的这项任务牢牢牵制住。

平面上有 $k$ 个圆环。对每个圆环，均匀采样 $n$ 个点，并加入微小的随机噪声。任务是仅根据这些带噪声的采样点，恢复出原始的圆环。

圆环及其采样点按如下方式生成：圆环中心在以原点为中心、半径为 $1\,000\,000$ 的圆盘内均匀随机采样；圆环半径则在区间 $[250\,000, 750\,000]$ 内均匀随机采样。设圆环 $R$ 的中心为 $(x, y)$、半径为 $r$。为从 $R$ 上采样一个点，首先在 $[0, 2\pi]$ 内均匀随机采样一个角度 $\theta$，再在 $[0.9r, 1.1r]$ 内均匀随机采样一个距离 $d$；然后该采样点的坐标为 $(x+d\cos(\theta), y+d\sin(\theta))$，并四舍五入至最接近的整数。

圆环之间的距离采用豪斯多夫距离（Hausdorff distance）度量。在本题中，两个圆环 $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$。

请牢记：人类能非常轻松地完成此任务，因此务必确保没有任何人类叛徒协助赛博人完成此项任务。

The first line contains an integer $k$ ($1 \leq k \leq 4$), the number of rings.

The second line contains an integer $n$ ($100 \leq n \leq 1\,000$), the number of samples per ring.

The following $n \times k$ lines contain the samples, one sample per line.

Each line contains a pair of integers $x_i, y_i$, where $(x_i, y_i)$ are the coordinates of the $i$-th sample.

第一行包含一个整数 $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$ 个采样点的坐标。

Print $k$ lines, each describing a single ring.

For each line, print three real numbers $x_i, y_i, r_i$, where $(x_i, y_i)$ and $r_i$ are the coordinates and the radius of the $i$-th ring.

The order of the rings does not matter.

输出 $k$ 行，每行描述一个环。

对于每一行，输出三个实数 $x_i, y_i, r_i$，其中 $(x_i, y_i)$ 和 $r_i$ 分别为第 $i$ 个环的圆心坐标和半径。

环的输出顺序无关紧要。

Here is how one of tests with $k=4$ and $n=100$ looks like.

You can download the sample input and output here.

以下是 $k=4$ 且 $n=100$ 的一个测试用例的示意图。

您可以在此处下载样例输入与输出文件：下载链接