Задание 27. Информатика. ЕГЭ. Поляков-7703
- Просмотры: 25
- Изменено: 24 ноября 2024
Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор не менее чем из 30 соседних звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров. Центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Расстояние между двумя точками \(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 100~000\), затем целую часть произведения \(P_y \times 100~000\) для файла А, во второй строке – аналогичные данные для файла Б.
Решение:
Точечная диаграмма, построенная для файла А в табличном процессоре, имеет вид
Левый кластер без аномалий находится в объединении областей \(x < 3, \, 1 < y < 9\) и \(x < 7, \, 1 < y < 6\). Правый кластер лежит в объединении областей \(x > 3, \, y > 6\) и \(7.25 < x < 10.25\).
Точечная диаграмма для файла Б, построенная в табличном процессоре, имеет вид
Верхний кластер лежит в объединении областей \(x > 1, \, y > 5.5\) и \(x > 8, \, y > 5\). Средний кластер лежит в объединении областей \(2 < x < 10, \, 2 < y < 5.5\) и \(7 < x < 10, \, 0 < y < 5.5\). Нижний кластер лежит в объединении областей \(-1 < x < 2, \, y < 5.5\) и \(2 < x < 7, \, y < 2\).
Python
def which_cluster(point, task):
x, y = point
match task:
case 1:
if (x < 3 and 1 < y < 9) or (x < 7 and 1 < y < 6):
return 0
elif (x > 3 and y > 6) or (7.25 < x < 10.25):
return 1
return -1
case 2:
if (x > 1 and y > 5.5) or (x > 8 and y > 5):
return 0
elif (2 < x < 10 and 2 < y < 5.5) or (7 < x < 10 and 0 < y < 5.5):
return 1
elif (-1 < x < 2 and y < 5.5) or (2 < x < 7 and y < 2):
return 2
return -1
def dist(p1, p2):
x1, y1 = p1
x2, y2 = p2
return ((x1 - x2)**2 + (y1 - y2)**2)**0.5
base = ''
files = ['27a.txt', '27b.txt']
nums_cls = [2, 3]
for task in (1, 2):
fd = open(base + files[task-1])
fd.readline()
clusters = [[], [], []]
num_cl = nums_cls[task-1]
for line in fd:
point = [float(d) for d in line.replace(',', '.').split()]
if which_cluster(point, task) != -1:
clusters[which_cluster(point, task)].append(point)
centers = []
for i in range(num_cl):
dmin = 10**1000
for p in clusters[i]:
d = sum(dist(p, p1) for p1 in clusters[i])
if d < dmin:
c = p
dmin = d
centers.append(c)
px = sum(p[0] for p in centers) / num_cl * 100_000
py = sum(p[1] for p in centers) / num_cl * 100_000
print(int(px), int(py))
Ответ:
\(515933 \,\, 498987\)
\(471077 \,\, 409201\)