Информатика. ЕГЭ
Задания для подготовки
Задачи разных лет из реальных экзаменов, демо-вариантов, сборников задач и других источников
Задание 27. Информатика. ЕГЭ. Поляков-7703
- Просмотры: 552
- Изменено: 1 февраля 2025
Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор не менее чем из 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\)
Обсуждение задания
Здесь пока нет ни одного комментария. Будьте первым!
Новый тренажёр-эмулятор
Станции КЕГЭ
Эффективно готовьтесь к ЕГЭ по информатике с новым тренажёром, эмулирующем работу станции КЕГЭ, которая используется на реальном экзамене.
Новое видео
Методы решения задания 16 ЕГЭ по Информатике «Вычисление рекуррентных выражений»
Поддержать автора сайта!
Поддержите автора сайта, если материалы, размещённые здесь, оказались вам полезны.
Совершая донат, вы соглашаетесь с Условиями использования