Открытый вариант КИМ ЕГЭ по информатике 2025. Задание 27 решение
Условие задачи
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников. Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется в евклидовой метрике.
Входные данные
В файле A хранятся координаты точек двух кластеров, где H = 3, W = 3 для каждого кластера. В каждой строке записана информация о расположении на карте одной точки: сначала координата x, затем координата y. Известно, что количество точек не превышает 1000. В файле Б хранятся координаты точек трёх кластеров, где H = 3, W = 3 для каждого кластера. Известно, что количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична файлу А. Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px – среднее арифметическое абсцисс центров кластеров, и Py – среднее арифметическое ординат центров кластеров.
В ответе запишите четыре числа: в первой строке сначала целую часть произведения Px × 10 000, затем целую часть произведения Py × 10 000 для файла А, во второй строке – аналогичные данные для файла Б.
Скачать вариант и файлы к нему можно на сайте ФИПИ.
Решение
Прочитаем данные из файла и переведем их в числа. Заметим, что в данных разделитель дробной части - запятая (этот формат более привычен для Excel, однако непривычен для Python, который требует точку в качестве разделителя).
def read_points(filename):
points = []
with open(filename, 'r') as f:
for line in f:
line = line.replace(",", ".")
points.append([float(coord) for coord in line.split()])
return points
Функция для кластеризации точек (учтем тот факт, что максимальное расстояние между двумя точками прямоугольника - это math.hypot(H, W)).
def clusterize_points(points, H, W, n_clusters):
max_dist = math.hypot(H, W)
clusters = [[] for _ in range(n_clusters)]
for point in points: # Цикл по всем точкам из файла
for cluster in clusters: # Для каждого кластера
for cluster_point in cluster: # Для каждой точки из кластера
if math.dist(point, cluster_point) > max_dist: # Если хотя бы одна из точек удалена больше, чем максимально возможное расстояние
break # Прекращаем проверки и пытаемся положить точку в следующий кластер
else: # Если точка все же оказалась близко ко всем точкам кластера
cluster.append(point) # Добавить в кластер и сразу перейти к следующей
break
return clusters
Функция для определения центра кластера
def find_cluster_center(cluster):
min_distance_sum = float('inf')
center = None
for point in cluster:
distance_sum = sum(math.dist(point, other) for other in cluster)
if distance_sum < min_distance_sum:
min_distance_sum = distance_sum
center = point
return center
И полная версия, с обработкой и выводом необходимых ответов:
import math
def read_points(filename):
points = []
with open(filename, 'r') as f:
for line in f:
line = line.replace(",", ".")
points.append([float(coord) for coord in line.split()])
return points
def find_cluster_center(cluster):
min_distance_sum = float('inf')
center = None
for point in cluster:
distance_sum = sum(math.dist(point, other) for other in cluster)
if distance_sum < min_distance_sum:
min_distance_sum = distance_sum
center = point
return center
def clusterize_points(points, H, W, n_clusters):
max_dist = math.hypot(H, W)
clusters = [[] for _ in range(n_clusters)]
for point in points: # Цикл по всем точкам из файла
for cluster in clusters: # Для каждого кластера
for cluster_point in cluster: # Для каждой точки из кластера
if math.dist(point, cluster_point) > max_dist: # Если хотя бы одна из точек удалена больше, чем максимально возможное расстояние
break # Прекращаем проверки и пытаемся положить точку в следующий кластер
else: # Если точка все же оказалась близко ко всем точкам кластера
cluster.append(point) # Добавить в кластер и сразу перейти к следующей
break
return clusters
def process_file(filename, H, W, n_clusters):
points = read_points(filename)
clusters = clusterize_points(points, H, W, n_clusters)
centers = [find_cluster_center(cluster) for cluster in clusters]
Px = sum(center[0] for center in centers) / len(centers)
Py = sum(center[1] for center in centers) / len(centers)
return int(Px * 10000), int(Py * 10000)
result_a = process_file("A.txt", 3, 3, 2)
result_b = process_file("B.txt", 3, 3, 3)
print(result_a[0], result_a[1])
print(result_b[0], result_b[1])
С одной стороны, задание стало проще, чем демо вариант 2024 года. Не надо придумывать сверхбыстрый алгоритм, даже с файлом B наивная реализация справляется за разумное время.
С другой стороны, задача теперь требует анализа данных, а не просто математический алгоритм, и это может быть сложнее.
Если остались вопросы - добро пожаловать в Telegram-канал!