---

import sys
import math
from stars import __stars
__stars()

def read_points_from_file(filename="stars.txt"):
    """
    Читает все точки из файла filename.
    Каждая строка - два числа x и y через пробел или табуляцию,
    десятичная часть может быть разделена запятой.
    Возвращает список точек [(x, y), …].
    """
    pts = []
    with open(filename, "r", encoding="utf-8") as f:
        for line in f:
            line = line.strip()
            if not line:
                continue

            parts = line.split()
            # Предполагаем, что по условию parts всегда длины 2
            x_str = parts[0].replace(",", ".")
            y_str = parts[1].replace(",", ".")
            x = float(x_str)
            y = float(y_str)
            pts.append((x, y))
    return pts

def split_clusters(pts):
    """
    Делит pts на два кластера по максимальному разрыву по оси X.
    """
    # Сортируем копию по x (кортежи сравниваются по первому элементу)
    sorted_pts = sorted(pts)

    # Ищем индекс, после которого разрыв по x будет максимальным
    max_gap = -1.0
    split_i = 0
    for i in range(len(sorted_pts) - 1):
        gap = sorted_pts[i+1][0] - sorted_pts[i][0]
        if gap > max_gap:
            max_gap = gap
            split_i = i

    # Порог для разбиения - середина самого большого разрыва
    x1 = sorted_pts[split_i][0]
    x2 = sorted_pts[split_i + 1][0]
    threshold = (x1 + x2) / 2.0

    # Собираем два кластера в два явных цикла
    c1 = []
    c2 = []
    for x, y in pts:
        if x <= threshold:
            c1.append((x, y))
        else:
            c2.append((x, y))

    return c1, c2

def total_distance(p, cluster):
    """
    Суммирует евклидовы расстояния от точки p до всех точек cluster.
    """
    total = 0.0
    for q in cluster:
        dx = p[0] - q[0]
        dy = p[1] - q[1]
        total += math.hypot(dx, dy)
    return total

def find_center(cluster):
    """
    Перебирает все точки cluster и возвращает ту, у которой
    сумма расстояний до остальных минимальна.
    """
    best_pt = cluster[0]
    best_sum = total_distance(best_pt, cluster)

    for p in cluster:
        curr_sum = total_distance(p, cluster)
        if curr_sum < best_sum:
            best_sum = curr_sum
            best_pt = p

    return best_pt

pts = read_points_from_file()

# разбиваем на два кластера
c1, c2 = split_clusters(pts)

# находим центры
ctr1 = find_center(c1)
ctr2 = find_center(c2)

# считаем средние Px, Py
px = (ctr1[0] + ctr2[0]) / 2.0
py = (ctr1[1] + ctr2[1]) / 2.0

# выводим целые части от умножения на 10000
ix = abs(int(px * 10000))
iy = abs(int(py * 10000))
print(ix, iy)

#Генератор исходного файла:
import random
def __generate_stars(
    n1: int = 50,
    n2: int = 50,
    center1: tuple[float, float] = (0.0, 0.0),
    center2: tuple[float, float] = (10.0, 10.0),
    sigma: float = 1.0,
    filename: str = "stars.txt"
) -> None:

    pts = []
    # Кластер 1
    for _ in range(n1):
        x = random.gauss(center1[0], sigma)
        y = random.gauss(center1[1], sigma)
        pts.append((x, y))
    # Кластер 2
    for _ in range(n2):
        x = random.gauss(center2[0], sigma)
        y = random.gauss(center2[1], sigma)
        pts.append((x, y))

    random.shuffle(pts)

    # Сохраняем в файл
    with open(filename, "w", encoding="utf-8") as f:
        for x, y in pts:
            f.write(f"{x} {y}\n")


def __stars():
    __generate_stars(
        n1=50,
        n2=50,
        center1=(0.0, 0.0),
        center2=(10.0, 10.0),
        sigma=1.5,
        filename="stars.txt"
    )