Задание высокого уровня сложности, на его выполнение отводится 40 минут. Проверяет умение выполнять последовательность действий по анализу данных.
Условие задачи
Учёный решил провести кластеризацию множества звёзд по их расположению на карте звёздного неба. Кластер звёзд — это набор звёзд (точек на графике), лежащих внутри прямоугольника высотой H и шириной W. Каждая звезда принадлежит только одному кластеру. Истинный центр кластера (центроид) — одна из звёзд, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Расстояние вычисляется по формуле евклидова расстояния между двумя точками на плоскости: √((x₂ — x₁)² + (y₂ — y₁)²)
В файле A хранятся данные о звёздах двух кластеров. В каждой строке записаны координаты одной звезды: сначала координата X, затем координата Y (в условных единицах). В файле B хранятся данные о звёздах трёх кластеров (количество звёзд не превышает 10 000). Структура файла B аналогична файлу A.
Необходимо определить координаты центра каждого кластера (центроида) для файлов A и B. В ответе для каждого файла нужно указать два числа:
- P(x) — средняя арифметическая абсцисс центров кластеров, умноженная на 10 000.
- P(y) — средняя арифметическая ординат центров кластеров, умноженная на 10 000.
Решение на языке Python
Для решения задачи используется язык программирования Python. Файлы A и B находятся в той же директории, что и скрипт.
Обработка данных
В файлах данные представлены вещественными числами, где целая и дробная части разделены запятой, а не точкой, как принято в Python. Поэтому запятые заменяются на точки. Данные из файлов читаются построчно. Первая строка, содержащая заголовок «XY», пропускается.
file = open("demo_a.txt", "r", encoding="utf-8")
file.readline() # пропускаем первую строку
cluster1 = []
cluster2 = []
for line in file:
x, y = map(float, line.replace(',', '.').split())
if 0 <= x <= 1 and 0 <= y <= 4:
cluster1.append((x, y))
elif 1 <= x <= 4.5 and 3 <= y <= 7:
cluster2.append((x, y))Функция поиска центроида
Функция find_centroid принимает список точек и возвращает координаты центроида:
def find_centroid(cluster):
min_dist = 10**100
x_center = 0
y_center = 0
for i, (x1, y1) in enumerate(cluster):
result = 0
for j, (x2, y2) in enumerate(cluster):
if i != j:
result += ((x2 - x1)**2 + (y2 - y1)**2)**0.5
if result < min_dist:
min_dist = result
x_center = x1
y_center = y1
return x_center, y_centerНахождение и вывод результата для файлов A и B
Функция find_centroid используется для нахождения центроидов кластеров в файлах A и B. Код для обработки файла B аналогичен обработке файла A, но с добавлением третьего кластера и соответствующим изменением вычисления среднего арифметического. Результат вычисляется согласно условию задачи.
# Обработка файла A (код аналогичен предыдущему разделу)
x1, y1 = find_centroid(cluster1)
x2, y2 = find_centroid(cluster2)
print(int((x1 + x2) / 2 * 10000), int((y1 + y2) / 2 * 10000))
#Обработка файла B (аналогично, но с тремя кластерами)
file = open("demo_b.txt", "r", encoding="utf-8")
file.readline()
cluster1 = []
cluster2 = []
cluster3 = []
# ... (код обработки данных аналогичен файлу A, но с тремя кластерами) ...
x1, y1 = find_centroid(cluster1)
x2, y2 = find_centroid(cluster2)
x3, y3 = find_centroid(cluster3)
print(int((x1 + x2 + x3) / 3 * 10000), int((y1 + y2 + y3) / 3 * 10000))Задача 27 демоверсии ЕГЭ по информатике 2025 года требует понимания принципов кластеризации и умения программировать на Python. Решение задачи включает в себя обработку данных из файлов, и написание функции для поиска центроидов. Результат вычисляется и выводится в соответствии с условием задачи. В результате для файла A получаем 10738 30730, а для файла B — 37522 893.