Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C3. Heidi and the Turing Test (Hard)

time limit per test

15 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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.

Input

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.

Output

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.

Note

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

You can download the sample input and output here.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/28/2020 19:18:44 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|