Информатика. ЕГЭ
Задания для подготовки
Задачи разных лет из реальных экзаменов, демо-вариантов, сборников задач и других источников
Задание 27. Информатика. ЕГЭ. Шастин. 19.09.2024
- Просмотры: 1474
- Изменено: 1 февраля 2025
(Л. Шастин) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд(точек) на графике, лежащий внутри прямоугольника высотой \(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=2\), \(W=2\) для каждого кластера. Известно, что количество звёзд не превышает \(10~000\). Структура хранения информации о звездах в файле Б аналогична файлу А.
Для каждого файла определите два кластера, расстояние между которыми минимально, и затем вычислите два числа: \(S_x\) — сумму координат абсцисс точек, образующих минимальное расстояние между этими кластерами, и \(S_y\) — сумму ординат этих точек.
В ответе запишите четыре числа: в первой строке сначала целую часть произведения \(S_x \times 1000\), затем целую часть произведения \(S_y \times 1000\) для файла А, во второй строке — аналогичные данные для файла Б.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла.
Решение:
Точечная диаграмма, построенная для файла А в табличном процессоре, имеет вид
Видно, что два кластера отчётливо разделяются прямой, проходящей через точки \(M (-2, \, 6)\) и \(N (4, \, 0)\). Уравнение прямой, проходящей через них, имеет вид \( x + y = 4\).
Точечная диаграмма для файла Б, построенная в табличном процессоре, имеет вид
Правый кластер можно отделить прямой \(x = 13\). Это будет кластер под номером \(0\). Четыре левых можно разбить на группы по два кластера прямой \(x = 8\). Правая двойка кластеров разделяется прямой \(y = 13\). Они будут иметь номера \(1\) (самый верхний) и \(2\). Левая двойка разделяется прямой \(y = 5\). Этим кластерам будет присвоены номера \(3\) и \(4\). Очевидно, что наименьшее расстояние нужно искать между кластерами \(1\) и \(2\), может быть между \(2\) и \(3\) кластерами (это на всякий случай рассмотрим), и между кластерами \(3\) и \(4\).
Python (3.10+)
def which_cluster(point, task):
x, y = point
match task:
case 0:
return int( x + y > 4)
case 1:
if x > 13:
return 0
elif x > 8:
if y > 13:
return 1
else:
return 2
else:
if y > 5:
return 3
return 4
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, 5]
min_dist_clust = [[(0, 1)], [(1, 2), (2, 3), (3, 4)]]
for t in [0, 1]:
data = [[], [], [], [], []]
for line in open(base + files[t]):
x, y = map(float, line.replace(',', '.').split())
data[which_cluster([x, y], t)].append([x, y])
dm = 10**100
for cl in min_dist_clust[t]:
for p1 in data[cl[0]]:
for p2 in data[cl[1]]:
d = dist(p1, p2)
if d < dm:
dm = d
p1m = p1
p2m = p2
sx = int((p1m[0] + p2m[0]) * 1000)
sy = int((p1m[1] + p2m[1]) * 1000)
print(sx, sy)
Ответ:
\(1731 \,\, 6256\)
\(18166 \,\, 26588\)
Обсуждение задания
Здесь пока нет ни одного комментария. Будьте первым!
Новый тренажёр-эмулятор
Станции КЕГЭ
Эффективно готовьтесь к ЕГЭ по информатике с новым тренажёром, эмулирующем работу станции КЕГЭ, которая используется на реальном экзамене.
Новое видео
Методы решения задания 16 ЕГЭ по Информатике «Вычисление рекуррентных выражений»
Поддержать автора сайта!
Поддержите автора сайта, если материалы, размещённые здесь, оказались вам полезны.
Совершая донат, вы соглашаетесь с Условиями использования