Кластеризация: центры кластеров

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между точками A(x1, y1) и B(x2, y2) вычисляется по формуле d(A, B) = √((x2 − x1)² + (y2 − y1)²).

В файле А хранятся координаты точек двух кластеров, где H = 6 и W = 5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (через пробел, дробная часть отделена точкой). Количество точек не превышает 1000.

В файле Б хранятся координаты точек трёх кластеров, где H = 5, W = 5 для каждого кластера. Количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична файлу А. Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, представляющих аномалии, которые возникли в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px — минимальную из абсцисс центров кластеров и Py — минимальную из ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 — расстояние между центрами кластеров с минимальным и максимальным количеством точек и Q2 — максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров. Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите четыре числа: в первой строке — сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке — сначала целую часть абсолютной величины Q1 × 10 000, затем Q2 × 10 000.

Файлы к варианту: Ege27_v1_A.txt (611 точек), Ege27_v1_B.txt (6690 точек).

from math import dist

def read(name):
    return [tuple(map(float, line.split())) for line in open(name) if line.strip()]

def split(points, centers, r=5.5):
    """Точка относится к кластеру, если она ближе r к его приблизительному центру (центры видны на графике)."""
    clusters = [[] for _ in centers]
    for p in points:
        for i, c in enumerate(centers):
            if dist(p, c) <= r:
                clusters[i].append(p)
                break                              # аномалии не попадают ни в один кластер
    return clusters

def center(cl):                                     # точка с наименьшей суммой расстояний до остальных
    return min(cl, key=lambda p: sum(dist(p, q) for q in cl))

# файл А
A = split(read('Ege27_v1_A.txt'), [(10, -14), (11, 12)])
cA = [center(cl) for cl in A]
px = min(c[0] for c in cA)
py = min(c[1] for c in cA)
print(int(abs(px) * 10000), int(abs(py) * 10000))
# файл Б
B = split(read('Ege27_v1_B.txt'), [(-2, -2), (-17, 17), (9, -9)])
cB = [center(cl) for cl in B]
small = min(range(len(B)), key=lambda i: len(B[i]))
large = max(range(len(B)), key=lambda i: len(B[i]))
q1 = dist(cB[small], cB[large])
q2 = max(dist(cB[i], p) for i in range(len(B)) for p in B[i])
print(int(q1 * 10000), int(q2 * 10000))

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между точками A(x1, y1) и B(x2, y2) вычисляется по формуле d(A, B) = √((x2 − x1)² + (y2 − y1)²).

В файле А хранятся координаты точек двух кластеров, где H = 4 и W = 3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (через пробел, дробная часть отделена точкой). Количество точек не превышает 1000.

В файле Б хранятся координаты точек трёх кластеров, где H = 6, W = 5 для каждого кластера. Количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична файлу А. Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, представляющих аномалии, которые возникли в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px — среднее арифметическое абсцисс центров кластеров и Py — среднее арифметическое ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 — расстояние между центрами кластеров с минимальным и максимальным количеством точек и Q2 — максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров. Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите четыре числа: в первой строке — сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке — сначала целую часть абсолютной величины Q1 × 10 000, затем Q2 × 10 000.

Файлы к варианту: Ege27_v2_A.txt (698 точек), Ege27_v2_B.txt (6209 точек).

from math import dist

def read(name):
    return [tuple(map(float, line.split())) for line in open(name) if line.strip()]

def split(points, centers, r=5.5):
    """Точка относится к кластеру, если она ближе r к его приблизительному центру (центры видны на графике)."""
    clusters = [[] for _ in centers]
    for p in points:
        for i, c in enumerate(centers):
            if dist(p, c) <= r:
                clusters[i].append(p)
                break                              # аномалии не попадают ни в один кластер
    return clusters

def center(cl):                                     # точка с наименьшей суммой расстояний до остальных
    return min(cl, key=lambda p: sum(dist(p, q) for q in cl))

# файл А
A = split(read('Ege27_v2_A.txt'), [(-6, 19), (2, 4)])
cA = [center(cl) for cl in A]
px = sum(c[0] for c in cA) / len(cA)
py = sum(c[1] for c in cA) / len(cA)
print(int(abs(px) * 10000), int(abs(py) * 10000))
# файл Б
B = split(read('Ege27_v2_B.txt'), [(19, 5), (-7, 19), (3, -14)])
cB = [center(cl) for cl in B]
small = min(range(len(B)), key=lambda i: len(B[i]))
large = max(range(len(B)), key=lambda i: len(B[i]))
q1 = dist(cB[small], cB[large])
q2 = max(dist(cB[i], p) for i in range(len(B)) for p in B[i])
print(int(q1 * 10000), int(q2 * 10000))

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между точками A(x1, y1) и B(x2, y2) вычисляется по формуле d(A, B) = √((x2 − x1)² + (y2 − y1)²).

В файле А хранятся координаты точек двух кластеров, где H = 6 и W = 4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (через пробел, дробная часть отделена точкой). Количество точек не превышает 1000.

В файле Б хранятся координаты точек трёх кластеров, где H = 6, W = 4 для каждого кластера. Количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична файлу А. Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, представляющих аномалии, которые возникли в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px — минимальную из абсцисс центров кластеров и Py — минимальную из ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 — максимальную из абсцисс центров кластеров и Q2 — максимальную из ординат центров кластеров.

В ответе запишите четыре числа: в первой строке — сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке — сначала целую часть абсолютной величины Q1 × 10 000, затем Q2 × 10 000.

Файлы к варианту: Ege27_v3_A.txt (688 точек), Ege27_v3_B.txt (5802 точек).

from math import dist

def read(name):
    return [tuple(map(float, line.split())) for line in open(name) if line.strip()]

def split(points, centers, r=5.5):
    """Точка относится к кластеру, если она ближе r к его приблизительному центру (центры видны на графике)."""
    clusters = [[] for _ in centers]
    for p in points:
        for i, c in enumerate(centers):
            if dist(p, c) <= r:
                clusters[i].append(p)
                break                              # аномалии не попадают ни в один кластер
    return clusters

def center(cl):                                     # точка с наименьшей суммой расстояний до остальных
    return min(cl, key=lambda p: sum(dist(p, q) for q in cl))

# файл А
A = split(read('Ege27_v3_A.txt'), [(4, 3), (-15, 19)])
cA = [center(cl) for cl in A]
px = min(c[0] for c in cA)
py = min(c[1] for c in cA)
print(int(abs(px) * 10000), int(abs(py) * 10000))
# файл Б
B = split(read('Ege27_v3_B.txt'), [(6, -12), (-5, 4), (-20, 14)])
cB = [center(cl) for cl in B]
q1 = max(c[0] for c in cB)
q2 = max(c[1] for c in cB)
print(int(abs(q1) * 10000), int(abs(q2) * 10000))

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между точками A(x1, y1) и B(x2, y2) вычисляется по формуле d(A, B) = √((x2 − x1)² + (y2 − y1)²).

В файле А хранятся координаты точек двух кластеров, где H = 4 и W = 3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (через пробел, дробная часть отделена точкой). Количество точек не превышает 1000.

В файле Б хранятся координаты точек трёх кластеров, где H = 5, W = 5 для каждого кластера. Количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична файлу А. Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, представляющих аномалии, которые возникли в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px — минимальную из абсцисс центров кластеров и Py — минимальную из ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 — расстояние между центрами кластеров с минимальным и максимальным количеством точек и Q2 — максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров. Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите четыре числа: в первой строке — сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке — сначала целую часть абсолютной величины Q1 × 10 000, затем Q2 × 10 000.

Файлы к варианту: Ege27_v4_A.txt (632 точек), Ege27_v4_B.txt (4335 точек).

from math import dist

def read(name):
    return [tuple(map(float, line.split())) for line in open(name) if line.strip()]

def split(points, centers, r=5.5):
    """Точка относится к кластеру, если она ближе r к его приблизительному центру (центры видны на графике)."""
    clusters = [[] for _ in centers]
    for p in points:
        for i, c in enumerate(centers):
            if dist(p, c) <= r:
                clusters[i].append(p)
                break                              # аномалии не попадают ни в один кластер
    return clusters

def center(cl):                                     # точка с наименьшей суммой расстояний до остальных
    return min(cl, key=lambda p: sum(dist(p, q) for q in cl))

# файл А
A = split(read('Ege27_v4_A.txt'), [(-2, -7), (-12, 11)])
cA = [center(cl) for cl in A]
px = min(c[0] for c in cA)
py = min(c[1] for c in cA)
print(int(abs(px) * 10000), int(abs(py) * 10000))
# файл Б
B = split(read('Ege27_v4_B.txt'), [(-7, -3), (20, -14), (16, 19)])
cB = [center(cl) for cl in B]
small = min(range(len(B)), key=lambda i: len(B[i]))
large = max(range(len(B)), key=lambda i: len(B[i]))
q1 = dist(cB[small], cB[large])
q2 = max(dist(cB[i], p) for i in range(len(B)) for p in B[i])
print(int(q1 * 10000), int(q2 * 10000))

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между точками A(x1, y1) и B(x2, y2) вычисляется по формуле d(A, B) = √((x2 − x1)² + (y2 − y1)²).

В файле А хранятся координаты точек двух кластеров, где H = 6 и W = 4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (через пробел, дробная часть отделена точкой). Количество точек не превышает 1000.

В файле Б хранятся координаты точек трёх кластеров, где H = 6, W = 5 для каждого кластера. Количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична файлу А. Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, представляющих аномалии, которые возникли в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px — среднее арифметическое абсцисс центров кластеров и Py — среднее арифметическое ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 — максимальную из абсцисс центров кластеров и Q2 — максимальную из ординат центров кластеров.

В ответе запишите четыре числа: в первой строке — сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке — сначала целую часть абсолютной величины Q1 × 10 000, затем Q2 × 10 000.

Файлы к варианту: Ege27_v5_A.txt (860 точек), Ege27_v5_B.txt (5392 точек).

from math import dist

def read(name):
    return [tuple(map(float, line.split())) for line in open(name) if line.strip()]

def split(points, centers, r=5.5):
    """Точка относится к кластеру, если она ближе r к его приблизительному центру (центры видны на графике)."""
    clusters = [[] for _ in centers]
    for p in points:
        for i, c in enumerate(centers):
            if dist(p, c) <= r:
                clusters[i].append(p)
                break                              # аномалии не попадают ни в один кластер
    return clusters

def center(cl):                                     # точка с наименьшей суммой расстояний до остальных
    return min(cl, key=lambda p: sum(dist(p, q) for q in cl))

# файл А
A = split(read('Ege27_v5_A.txt'), [(-14, 8), (9, -4)])
cA = [center(cl) for cl in A]
px = sum(c[0] for c in cA) / len(cA)
py = sum(c[1] for c in cA) / len(cA)
print(int(abs(px) * 10000), int(abs(py) * 10000))
# файл Б
B = split(read('Ege27_v5_B.txt'), [(13, 6), (2, 13), (-14, 9)])
cB = [center(cl) for cl in B]
q1 = max(c[0] for c in cB)
q2 = max(c[1] for c in cB)
print(int(abs(q1) * 10000), int(abs(q2) * 10000))

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между точками A(x1, y1) и B(x2, y2) вычисляется по формуле d(A, B) = √((x2 − x1)² + (y2 − y1)²).

В файле А хранятся координаты точек двух кластеров, где H = 6 и W = 4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (через пробел, дробная часть отделена точкой). Количество точек не превышает 1000.

В файле Б хранятся координаты точек трёх кластеров, где H = 5, W = 5 для каждого кластера. Количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична файлу А. Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, представляющих аномалии, которые возникли в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px — минимальную из абсцисс центров кластеров и Py — минимальную из ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 — расстояние между центрами кластеров с минимальным и максимальным количеством точек и Q2 — максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров. Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите четыре числа: в первой строке — сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке — сначала целую часть абсолютной величины Q1 × 10 000, затем Q2 × 10 000.

Файлы к варианту: Ege27_v6_A.txt (703 точек), Ege27_v6_B.txt (6672 точек).

from math import dist

def read(name):
    return [tuple(map(float, line.split())) for line in open(name) if line.strip()]

def split(points, centers, r=5.5):
    """Точка относится к кластеру, если она ближе r к его приблизительному центру (центры видны на графике)."""
    clusters = [[] for _ in centers]
    for p in points:
        for i, c in enumerate(centers):
            if dist(p, c) <= r:
                clusters[i].append(p)
                break                              # аномалии не попадают ни в один кластер
    return clusters

def center(cl):                                     # точка с наименьшей суммой расстояний до остальных
    return min(cl, key=lambda p: sum(dist(p, q) for q in cl))

# файл А
A = split(read('Ege27_v6_A.txt'), [(-2, -1), (13, -20)])
cA = [center(cl) for cl in A]
px = min(c[0] for c in cA)
py = min(c[1] for c in cA)
print(int(abs(px) * 10000), int(abs(py) * 10000))
# файл Б
B = split(read('Ege27_v6_B.txt'), [(18, 5), (-7, -17), (-17, -3)])
cB = [center(cl) for cl in B]
small = min(range(len(B)), key=lambda i: len(B[i]))
large = max(range(len(B)), key=lambda i: len(B[i]))
q1 = dist(cB[small], cB[large])
q2 = max(dist(cB[i], p) for i in range(len(B)) for p in B[i])
print(int(q1 * 10000), int(q2 * 10000))

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между точками A(x1, y1) и B(x2, y2) вычисляется по формуле d(A, B) = √((x2 − x1)² + (y2 − y1)²).

В файле А хранятся координаты точек двух кластеров, где H = 6 и W = 4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (через пробел, дробная часть отделена точкой). Количество точек не превышает 1000.

В файле Б хранятся координаты точек трёх кластеров, где H = 6, W = 5 для каждого кластера. Количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична файлу А. Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, представляющих аномалии, которые возникли в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px — среднее арифметическое абсцисс центров кластеров и Py — среднее арифметическое ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 — расстояние между центрами кластеров с минимальным и максимальным количеством точек и Q2 — максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров. Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите четыре числа: в первой строке — сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке — сначала целую часть абсолютной величины Q1 × 10 000, затем Q2 × 10 000.

Файлы к варианту: Ege27_v7_A.txt (740 точек), Ege27_v7_B.txt (5140 точек).

from math import dist

def read(name):
    return [tuple(map(float, line.split())) for line in open(name) if line.strip()]

def split(points, centers, r=5.5):
    """Точка относится к кластеру, если она ближе r к его приблизительному центру (центры видны на графике)."""
    clusters = [[] for _ in centers]
    for p in points:
        for i, c in enumerate(centers):
            if dist(p, c) <= r:
                clusters[i].append(p)
                break                              # аномалии не попадают ни в один кластер
    return clusters

def center(cl):                                     # точка с наименьшей суммой расстояний до остальных
    return min(cl, key=lambda p: sum(dist(p, q) for q in cl))

# файл А
A = split(read('Ege27_v7_A.txt'), [(3, 12), (8, -11)])
cA = [center(cl) for cl in A]
px = sum(c[0] for c in cA) / len(cA)
py = sum(c[1] for c in cA) / len(cA)
print(int(abs(px) * 10000), int(abs(py) * 10000))
# файл Б
B = split(read('Ege27_v7_B.txt'), [(7, -8), (-6, -8), (-5, 19)])
cB = [center(cl) for cl in B]
small = min(range(len(B)), key=lambda i: len(B[i]))
large = max(range(len(B)), key=lambda i: len(B[i]))
q1 = dist(cB[small], cB[large])
q2 = max(dist(cB[i], p) for i in range(len(B)) for p in B[i])
print(int(q1 * 10000), int(q2 * 10000))

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между точками A(x1, y1) и B(x2, y2) вычисляется по формуле d(A, B) = √((x2 − x1)² + (y2 − y1)²).

В файле А хранятся координаты точек двух кластеров, где H = 5 и W = 4 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (через пробел, дробная часть отделена точкой). Количество точек не превышает 1000.

В файле Б хранятся координаты точек трёх кластеров, где H = 7, W = 5 для каждого кластера. Количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична файлу А. Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, представляющих аномалии, которые возникли в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px — минимальную из абсцисс центров кластеров и Py — минимальную из ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 — расстояние между центрами кластеров с минимальным и максимальным количеством точек и Q2 — максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров. Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите четыре числа: в первой строке — сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке — сначала целую часть абсолютной величины Q1 × 10 000, затем Q2 × 10 000.

Файлы к варианту: Ege27_v8_A.txt (644 точек), Ege27_v8_B.txt (6396 точек).

from math import dist

def read(name):
    return [tuple(map(float, line.split())) for line in open(name) if line.strip()]

def split(points, centers, r=5.5):
    """Точка относится к кластеру, если она ближе r к его приблизительному центру (центры видны на графике)."""
    clusters = [[] for _ in centers]
    for p in points:
        for i, c in enumerate(centers):
            if dist(p, c) <= r:
                clusters[i].append(p)
                break                              # аномалии не попадают ни в один кластер
    return clusters

def center(cl):                                     # точка с наименьшей суммой расстояний до остальных
    return min(cl, key=lambda p: sum(dist(p, q) for q in cl))

# файл А
A = split(read('Ege27_v8_A.txt'), [(3, 9), (8, -17)])
cA = [center(cl) for cl in A]
px = min(c[0] for c in cA)
py = min(c[1] for c in cA)
print(int(abs(px) * 10000), int(abs(py) * 10000))
# файл Б
B = split(read('Ege27_v8_B.txt'), [(0, 12), (-1, -10), (8, 0)])
cB = [center(cl) for cl in B]
small = min(range(len(B)), key=lambda i: len(B[i]))
large = max(range(len(B)), key=lambda i: len(B[i]))
q1 = dist(cB[small], cB[large])
q2 = max(dist(cB[i], p) for i in range(len(B)) for p in B[i])
print(int(q1 * 10000), int(q2 * 10000))

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между точками A(x1, y1) и B(x2, y2) вычисляется по формуле d(A, B) = √((x2 − x1)² + (y2 − y1)²).

В файле А хранятся координаты точек двух кластеров, где H = 4 и W = 3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (через пробел, дробная часть отделена точкой). Количество точек не превышает 1000.

В файле Б хранятся координаты точек трёх кластеров, где H = 7, W = 5 для каждого кластера. Количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична файлу А. Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, представляющих аномалии, которые возникли в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px — среднее арифметическое абсцисс центров кластеров и Py — среднее арифметическое ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 — максимальную из абсцисс центров кластеров и Q2 — максимальную из ординат центров кластеров.

В ответе запишите четыре числа: в первой строке — сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке — сначала целую часть абсолютной величины Q1 × 10 000, затем Q2 × 10 000.

Файлы к варианту: Ege27_v9_A.txt (654 точек), Ege27_v9_B.txt (6221 точек).

from math import dist

def read(name):
    return [tuple(map(float, line.split())) for line in open(name) if line.strip()]

def split(points, centers, r=5.5):
    """Точка относится к кластеру, если она ближе r к его приблизительному центру (центры видны на графике)."""
    clusters = [[] for _ in centers]
    for p in points:
        for i, c in enumerate(centers):
            if dist(p, c) <= r:
                clusters[i].append(p)
                break                              # аномалии не попадают ни в один кластер
    return clusters

def center(cl):                                     # точка с наименьшей суммой расстояний до остальных
    return min(cl, key=lambda p: sum(dist(p, q) for q in cl))

# файл А
A = split(read('Ege27_v9_A.txt'), [(11, 15), (5, -7)])
cA = [center(cl) for cl in A]
px = sum(c[0] for c in cA) / len(cA)
py = sum(c[1] for c in cA) / len(cA)
print(int(abs(px) * 10000), int(abs(py) * 10000))
# файл Б
B = split(read('Ege27_v9_B.txt'), [(-13, 12), (-4, -14), (6, -3)])
cB = [center(cl) for cl in B]
q1 = max(c[0] for c in cB)
q2 = max(c[1] for c in cB)
print(int(abs(q1) * 10000), int(abs(q2) * 10000))

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между точками A(x1, y1) и B(x2, y2) вычисляется по формуле d(A, B) = √((x2 − x1)² + (y2 − y1)²).

В файле А хранятся координаты точек двух кластеров, где H = 6 и W = 5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (через пробел, дробная часть отделена точкой). Количество точек не превышает 1000.

В файле Б хранятся координаты точек трёх кластеров, где H = 7, W = 5 для каждого кластера. Количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична файлу А. Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, представляющих аномалии, которые возникли в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px — минимальную из абсцисс центров кластеров и Py — минимальную из ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 — расстояние между центрами кластеров с минимальным и максимальным количеством точек и Q2 — максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров. Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите четыре числа: в первой строке — сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке — сначала целую часть абсолютной величины Q1 × 10 000, затем Q2 × 10 000.

Файлы к варианту: Ege27_v10_A.txt (704 точек), Ege27_v10_B.txt (5126 точек).

from math import dist

def read(name):
    return [tuple(map(float, line.split())) for line in open(name) if line.strip()]

def split(points, centers, r=5.5):
    """Точка относится к кластеру, если она ближе r к его приблизительному центру (центры видны на графике)."""
    clusters = [[] for _ in centers]
    for p in points:
        for i, c in enumerate(centers):
            if dist(p, c) <= r:
                clusters[i].append(p)
                break                              # аномалии не попадают ни в один кластер
    return clusters

def center(cl):                                     # точка с наименьшей суммой расстояний до остальных
    return min(cl, key=lambda p: sum(dist(p, q) for q in cl))

# файл А
A = split(read('Ege27_v10_A.txt'), [(20, 18), (-4, 0)])
cA = [center(cl) for cl in A]
px = min(c[0] for c in cA)
py = min(c[1] for c in cA)
print(int(abs(px) * 10000), int(abs(py) * 10000))
# файл Б
B = split(read('Ege27_v10_B.txt'), [(8, -13), (20, 3), (-7, 1)])
cB = [center(cl) for cl in B]
small = min(range(len(B)), key=lambda i: len(B[i]))
large = max(range(len(B)), key=lambda i: len(B[i]))
q1 = dist(cB[small], cB[large])
q2 = max(dist(cB[i], p) for i in range(len(B)) for p in B[i])
print(int(q1 * 10000), int(q2 * 10000))

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между точками A(x1, y1) и B(x2, y2) вычисляется по формуле d(A, B) = √((x2 − x1)² + (y2 − y1)²).

В файле А хранятся координаты точек двух кластеров, где H = 6 и W = 5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (через пробел, дробная часть отделена точкой). Количество точек не превышает 1000.

В файле Б хранятся координаты точек трёх кластеров, где H = 5, W = 5 для каждого кластера. Количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична файлу А. Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, представляющих аномалии, которые возникли в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px — минимальную из абсцисс центров кластеров и Py — минимальную из ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 — расстояние между центрами кластеров с минимальным и максимальным количеством точек и Q2 — максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров. Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите четыре числа: в первой строке — сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке — сначала целую часть абсолютной величины Q1 × 10 000, затем Q2 × 10 000.

Файлы к варианту: Ege27_v11_A.txt (645 точек), Ege27_v11_B.txt (5267 точек).

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между точками A(x1, y1) и B(x2, y2) вычисляется по формуле d(A, B) = √((x2 − x1)² + (y2 − y1)²).

В файле А хранятся координаты точек двух кластеров, где H = 5 и W = 4 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (через пробел, дробная часть отделена точкой). Количество точек не превышает 1000.

В файле Б хранятся координаты точек трёх кластеров, где H = 6, W = 5 для каждого кластера. Количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична файлу А. Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, представляющих аномалии, которые возникли в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px — среднее арифметическое абсцисс центров кластеров и Py — среднее арифметическое ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 — расстояние между центрами кластеров с минимальным и максимальным количеством точек и Q2 — максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров. Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите четыре числа: в первой строке — сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке — сначала целую часть абсолютной величины Q1 × 10 000, затем Q2 × 10 000.

Файлы к варианту: Ege27_v12_A.txt (818 точек), Ege27_v12_B.txt (5027 точек).

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между точками A(x1, y1) и B(x2, y2) вычисляется по формуле d(A, B) = √((x2 − x1)² + (y2 − y1)²).

В файле А хранятся координаты точек двух кластеров, где H = 5 и W = 4 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (через пробел, дробная часть отделена точкой). Количество точек не превышает 1000.

В файле Б хранятся координаты точек трёх кластеров, где H = 7, W = 5 для каждого кластера. Количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична файлу А. Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, представляющих аномалии, которые возникли в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px — минимальную из абсцисс центров кластеров и Py — минимальную из ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 — максимальную из абсцисс центров кластеров и Q2 — максимальную из ординат центров кластеров.

В ответе запишите четыре числа: в первой строке — сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке — сначала целую часть абсолютной величины Q1 × 10 000, затем Q2 × 10 000.

Файлы к варианту: Ege27_v13_A.txt (686 точек), Ege27_v13_B.txt (5586 точек).

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между точками A(x1, y1) и B(x2, y2) вычисляется по формуле d(A, B) = √((x2 − x1)² + (y2 − y1)²).

В файле А хранятся координаты точек двух кластеров, где H = 5 и W = 4 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (через пробел, дробная часть отделена точкой). Количество точек не превышает 1000.

В файле Б хранятся координаты точек трёх кластеров, где H = 7, W = 5 для каждого кластера. Количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична файлу А. Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, представляющих аномалии, которые возникли в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px — среднее арифметическое абсцисс центров кластеров и Py — среднее арифметическое ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 — расстояние между центрами кластеров с минимальным и максимальным количеством точек и Q2 — максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров. Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите четыре числа: в первой строке — сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке — сначала целую часть абсолютной величины Q1 × 10 000, затем Q2 × 10 000.

Файлы к варианту: Ege27_v14_A.txt (730 точек), Ege27_v14_B.txt (4224 точек).

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между точками A(x1, y1) и B(x2, y2) вычисляется по формуле d(A, B) = √((x2 − x1)² + (y2 − y1)²).

В файле А хранятся координаты точек двух кластеров, где H = 6 и W = 5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (через пробел, дробная часть отделена точкой). Количество точек не превышает 1000.

В файле Б хранятся координаты точек трёх кластеров, где H = 5, W = 5 для каждого кластера. Количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична файлу А. Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, представляющих аномалии, которые возникли в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px — минимальную из абсцисс центров кластеров и Py — минимальную из ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 — расстояние между центрами кластеров с минимальным и максимальным количеством точек и Q2 — максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров. Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите четыре числа: в первой строке — сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке — сначала целую часть абсолютной величины Q1 × 10 000, затем Q2 × 10 000.

Файлы к варианту: Ege27_v15_A.txt (665 точек), Ege27_v15_B.txt (4420 точек).