Задание 27. Информатика. ЕГЭ. Поляков-7600
- Просмотры: 257
- Изменено: 1 февраля 2025
Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров. Центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Расстояние между двумя точками
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа:
Решение:
Точечная диаграмма, построенная для файла А в табличном процессоре, имеет вид
Видно, что два кластера отчётливо разделяются прямой, проходящей через точки
Точечная диаграмма Б, построенная в табличном процессоре, имеет вид
Правый верхний кластер можно отделить прямой, проходящей через точки
Python (3.10+)
def which_cluster(point, task):
x, y = point
match task:
case 0:
return int(2 * x + y > 4)
case 1:
if 3 * x + 2 * y > 33:
return 0
elif 7 * y - 9 * x > 12.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)
Ответ: