Задание 27. Информатика. ЕГЭ. Демо-2025
- Просмотры: 552
- Изменено: 24 ноября 2024
Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд(точек) на графике, лежащий внутри прямоугольника высотой \(H\) и шириной \(W\). Каждая звезда обязательно принадлежит только одному из кластеров.
Истинный центр кластера или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками \(A \,(x_1, \, y_1)\) и \(B \, (x_2, \, y_2)\) на плоскости, которое вычисляется по формуле: $$ d(A, \, B) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} $$ В файле A хранятся данные о звёздах двух кластеров, где \(H=3\), \(W=3\) для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата \(x\), затем координата \(y\). Значения даны в условных единицах. Известно, что количество звёзд не превышает \(1000.\)
В файле Б хранятся данные о звёздах трёх кластеров, где \(H=3\), \(W=3\) для каждого кластера. Известно, что количество звёзд не превышает \(10~000\). Структура хранения информации о звездах в файле Б аналогична файлу А.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: \(P_x\) – среднее арифметическое абсцисс центров кластеров, и \(P_y\) – среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения \(P_x \times 10~000\) , затем целую часть произведения \(P_y \times 10~000\) для файла А, во второй строке – аналогичные данные для файла Б.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла.
Решение:
Точечная диаграмма распределения звёзд по координатам, построенная в табличном процессоре, имеет вид:
Видно, что кластеры разделены друг от друга прямой \(y = 3\). Используем это для разбиения звёзд по кластерам
Python
files = ['demo_2025_27_А.txt']
base = ''
def dist(p1, p2):
return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)**0.5
for fn in files:
data = [[], []]
fdesc = open(base + fn)
fdesc.readline()
for line in fdesc:
x, y = map(float, line.replace(',', '.').split())
if y < 3:
data[0].append([x, y])
else:
data[1].append([x, y])
centers = [[], []]
for k in [0, 1]:
dm = 10**100
for i in range(len(data[k])):
d = sum(dist(data[k][i], p) for p in data[k])
if d < dm:
centers[k] = [data[k][i][0], data[k][i][1]]
dm = d
print(int((centers[0][0] + centers[1][0]) / 2 * 10000), int((centers[0][1] + centers[1][1]) / 2 * 10000))
Аналогично, для файла Б имеем такую точечную диаграмму:
Здесь один кластер отделён от двух других прямой \(y = 4\). Два оставшихся кластера, очевидно, разделяются прямой \(x = 5\). Получаем
Python
files = ['demo_2025_27_Б.txt']
base = ''
def dist(p1, p2):
return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)**0.5
for fn in files:
data = [[], [], []]
fdesc = open(base + fn)
fdesc.readline()
for line in fdesc:
x, y = map(float, line.replace(',', '.').split())
if y < 4:
data[0].append([x, y])
elif x < 5:
data[1].append([x, y])
else:
data[2].append([x, y])
centers = [[], [], []]
for k in [0, 1, 2]:
dm = 10**100
for i in range(len(data[k])):
d = sum(dist(data[k][i], p) for p in data[k])
if d < dm:
centers[k] = [data[k][i][0], data[k][i][1]]
dm = d
print(int((centers[0][0] + centers[1][0] + centers[2][0]) / 3 * 10000), int((centers[0][1] + centers[1][1] + centers[2][1]) / 3 * 10000))
Ответ:
\(10738 \,\, 30730\)
\(37522 \,\, 51277\)