# Lonely Circle

*English translation by SOTA – AI Community of the Russian original. Organisers who would like this translation removed can email sota.ai.community@gmail.com.*

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

**Points for the task:** 50<br>
**Answer submission format:** program code<br>
**Number of attempts:** 100<br>
**Submission that counts:** the last one<br>
**Time limit:** 10 seconds<br>
**Memory limit:** 64 MB<br>
**Input:** standard input or input.txt<br>
**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:

```python
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**

```text
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**

```text
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](https://vos.olimpiada.ru/upload/files/Arhive_tasks/2025-26/reg/ai/tasks-ai-9-11-tur1-reg-25-26.pdf).]*