Person in Charge

• 035966_L3

Attention

This problem requires file I/O (circle.in / circle.out).

Problem Description

There is a $1000 \times 1000$ plane. A Cartesian coordinate system is established with the bottom-left corner as the origin, and the top-right corner is denoted as $(1000,1000)$. Thus, each point can be uniquely represented by its coordinates.

Sleeping Cat drew a circle with a radius no less than $\bm{100}$ inside the plane and then uniformly randomly selected $10^5$ points on the plane.

Sleeping Cat did not tell you the center or radius of the circle, and you need to deduce it. However, Sleeping Cat won't leave you completely in the dark—he provided the relative positions of the $10^5$ points with respect to the circle (whether they are inside the circle, with points exactly on the circle treated as inside).

Input Format

$10^5$ lines, each containing two $3$-decimal-place numbers $x, y$ and an integer $z$ (guaranteed to be $\bm 0$ or $\bm 1$), representing the coordinates $(x, y)$ of a point and its relative position $z$ ($\bm{z=1}$ means inside the circle, $\bm{z=0}$ means outside).

Output Format

The first line should contain two real numbers $x_0, y_0$, representing the center $(x_0, y_0)$ of the circle.

The second line should contain a real number $r_0$, representing the radius of the circle.

Scoring Details

You will score $0$ points if:

• Your program fails to run or produces incorrect output format.
• The output does not satisfy $0 \le x_0, y_0, r_0 \le 1000$.

Otherwise:

• If the Euclidean distance between your provided center and the actual center is no more than $10$ units, you score $50$ points.
• If the absolute difference between your provided radius and the actual radius is no more than $10$ units, you score $50$ points.
• These two parts are scored independently.

Attachments

Download the files here.

We provided gen.cpp as the Generator but did not provide sample files.

After compiling gen.cpp into an executable gen, use the following command to generate the sample:

• gen circle.in circle.ans (Windows).
• ./gen circle.in circle.ans (Linux).

Official Solution

link