Задание 27. Информатика. ЕГЭ. Шастин. 19.09.2024
- Просмотры: 364
- Изменено: 24 ноября 2024
(Л. Шастин) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд(точек) на графике, лежащий внутри прямоугольника высотой \(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\)