Задание 27. Информатика. ЕГЭ. Поляков-7598
- Просмотры: 120
- Изменено: 24 ноября 2024
Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров. Центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Расстояние между двумя точками \(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 и файл Б). В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата \(x\), затем координата \(y\) (в условных единицах). Известно, что количество звёзд не превышает \(1000\). В файле Б хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает \(10~000\). Структура хранения информации о звездах в файле Б аналогична файлу А. Возможные данные одного из файлов иллюстрированы графиком.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: \(P_x\) – среднее арифметическое абсцисс центров кластеров, и \(P_y\) – среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения \(P_x \times 10~000\), затем целую часть произведения \(P_y \times 10~000\) для файла А, во второй строке – аналогичные данные для файла Б.
Решение:
Точечная диаграмма, построенная для файла А в табличном процессоре, имеет вид
Видно, что два кластера отчётливо разделяются прямой, проходящей через точки \(M (-2, \, 3)\) и \(N (2, \,\)\(-2)\). Уравнение прямой, проходящей через них, имеет вид \( 5x + 4y = 2\).
Точечная диаграмма Б, построенная в табличном процессоре, имеет вид
Разделим кластеры прямыми, исходящими из одной точки \(R(5.5, \, 4)\). Одна прямая (оранжевая) — это \(x = 5.5\). Красная прямая проходит ещё через точку \((2, \, 1)\), поэтому, нетрудно определить её уравнение: \(6x - 7y = 5\). Зелёная прямая проходит через точку \((9, \, 2.5)\) и имеет своим уравнением \(3x + 7y = 44.5\). Кластер \(0\) лежит левее оранжевой прямой, т.е все его точки имеют координаты с \(x < 5.5\), а также выше красной прямой, т.е. в области \(6x - 7y < 5\). Кластер \(1\) лежит правее прямой \(x = 5.5\) и выше зелёной прямой, т.е. в области \(3x + 7y > 44.5\).
Python (3.10+)
def which_cluster(point, task):
x, y = point
match task:
case 0:
return int(5 * x + 4 * y > 2)
case 1:
if 6 * x - 7 * y < 5 and x < 5.5:
return 0
elif x > 5.5 and 3 * x + 7 * y > 44.5:
return 1
return 2
def dist(point1, point2):
x1, y1 = point1
x2, y2 = point2
return ((x1 - x2)**2 + (y1 - y2)**2)**0.5
base = ''
files = ['27A.txt', '27B.txt']
clusters = [2, 3]
for t in [0, 1]:
fd = open(base + files[t])
fd.readline()
data = [[], [], []]
for line in fd:
x, y = map(float, line.replace(',', '.').split())
data[which_cluster([x, y], t)].append([x, y])
centers = []
for k in range(clusters[t]):
dm = 10**100
c = [0, 0]
for p in data[k]:
d = sum(dist(p, pt) for pt in data[k])
if d < dm:
dm = d
c = p
centers.append(c)
px = int(sum(c[0] for c in centers) / clusters[t] * 10000)
py = int(sum(c[1] for c in centers) / clusters[t] * 10000)
print(px, py)
Ответ:
\(-5013 \,\, 10862\)
\(53853 \,\, 38954\)