Lonely Circle

Lonely Circle

English translation by SOTA – AI Community of the Russian original. Organisers who would like this translation removed can email [email protected].

All-Russian School Olympiad in Informatics 2025–2026, Regional Stage, Grades 9–11
“Artificial Intelligence” profile, Tour 1, 17 January 2026
Task H

Points for the task: 50
Answer submission format: program code
Number of attempts: 100
Submission that counts: the last one
Time limit: 10 seconds
Memory limit: 64 MB
Input: standard input or input.txt
Output: standard output or output.txt

Statement

Andrey is preparing for an interview for a machine learning internship. To understand the basic ideas of classification, he started with the simplest case: if the points of two classes on the plane can be separated by a line, then the support vector machine (SVM) builds a separating line

$$w_1 x + w_2 y + b = 0,$$

and the sign of the expression $w_1 x + w_2 y + b$ determines which class a point belongs to (on one side of the line all points will have the sign $+$, and on the other side, $-$).

This is how Andrey became acquainted with linear classification.

He found a simple code example that shows how to read points from standard input, write them into a table with the columns x, y, label, and train a linear SVM on this data:

import sys
import pandas as pd
from sklearn.svm import SVC

def read_points():
    data = []
    tokens = sys.stdin.read().split()
    it = iter(tokens)

    n = int(next(it))
    for _ in range(n):
        x = float(next(it))
        y = float(next(it))
        label = int(next(it))
        data.append((x, y, label))

    df = pd.DataFrame(data, columns=["x", "y", "label"])
    return df

df = read_points()

clf = SVC(kernel="linear")
clf.fit(df[["x", "y"]], df["label"])

w1, w2 = clf.coef_[0]
b = clf.intercept_[0]
print(w1, w2, b)

At the interview, however, Andrey was given a different task.

Points on the plane with class labels $-1$ and $+1$ are given. It is guaranteed that there exists a circle with centre $(x_0, y_0)$ and radius $R > 0$ such that

• all points of class $-1$ lie strictly inside this circle;
• all points of class $+1$ lie strictly outside this circle.

You need to find any such circle $(x_0, y_0, R)$.

Help Andrey solve this problem and pass the interview!

Input format

The first line contains an integer $n$ ($3 \le n \le 10^5$). Then $n$ lines follow, each with three real numbers $x_i$, $y_i$, $label_i$: the coordinates of the next point and its label.

It is guaranteed that $|x_i|, |y_i| \le 10^9$.

Output format

Output three real numbers $x$, $y$ and $R$: the coordinates and the radius of the separating circle.

Scoring

Each test passed gives you 1 point.

The maximum possible score for the task is 50.

Test results are available during the tour.

Example

Input

10
0 0 -1
1 1 -1
2 0 -1
-2 0 -1
0 2 -1
4 0 1
-4 0 1
0 4 1
3 4 1
4 3 1

Output

0 0 3

Notes

This picture corresponds to the first example.

Orange points correspond to $label = -1$, blue points correspond to $label = 1$.

[Figure: the points of the example (label $-1$ as orange crosses, label $1$ as blue dots) and the circle with centre $(0, 0)$ and radius $3$ on a grid from $-5$ to $5$; see page 12 of the original statement.]