РЕШУ ЕГЭ — информатика

Задания

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.

Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть межкластерным диаметром двух кластеров максимальное расстояние между двумя точками, одна из которых принадлежит одному кластеру, а вторая  — другому. Для каждой пары кластеров гарантируется, что межкластерный диаметр образует единственная пара точек. Расстояние между двумя точками на плоскости A(x₁, y₁) и B(x₂, y₂) вычисляется по формуле:

$d левая круглая скобка A, B правая круглая скобка = корень из: начало аргумента: левая круглая скобка x_2 минус x_1 правая круглая скобка в квадрате плюс левая круглая скобка y_2 минус y_1 правая круглая скобка в квадрате конец аргумента .$

В файле A хранятся данные о звёздах двух кластеров, где H  =  6, W  =  5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

В файле Б хранятся данные о звёздах трёх кластеров, где H  =  6, W  =  5 для каждого кластера. Известно, что количество звёзд не превышает 10 000.

Файл А

Файл Б

Структура хранения информации о звёздах в файле Б аналогична структуре в файле A.

Известно, что в файле Б имеются координаты ровно четырёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти четыре точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для обоих файлов определите межкластерные диаметры для каждой пары различных кластеров. Для файла А найдите два числа: P_x  — модуль разности абсцисс точек, образующих межкластерный диаметр и P_y – сумму ординат точек, образующих межкластерный диаметр. Для файла Б найдите два числа: Q₁  — сумму всех межкластерных диаметров и Q₂  — максимальное расстояние от какой-либо точки, образующей межкластерный диаметр, до точки с координатами (1, 1).

В ответе запишите четыре числа: в первой строке – сначала целую часть произведения P_x × 1000, затем целую часть абсолютного значения произведения P_y × 1000; во второй строке – сначала целую часть произведения Q₁ × 100, затем целую часть произведения Q₂ × 100. Возможные данные одного из файлов иллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.

Для выполнения задания используйте данные из прилагаемого файла.

Ответ:

Решение. ##Приведём решение на языке Python для файла А.

from math import dist

data = []

for s in open('27a.txt'):

x, y = [float(d) for d in s.replace(',', '.').split()]

data.append([x, y])

rast = 2

clusters = []

while data:

cl = [data.pop()]

for p in cl:

sosed = [p1 for p1 in data if dist(p, p1) < rast]

for p1 in sosed:

cl.append(p1)

data.remove(p1)

clusters.append(cl)

clusters.sort(key=len)

def rast_clast(cluster1, cluster2):

res = []

for s1 in cluster1:

for s2 in cluster2:

res.append([dist(s1,s2), s1, s2])

return max(res)

mez_diam = rast_clast(clusters[0], clusters[1])

Px = abs(mez_diam[1][0] - mez_diam[2][0]) *1000

Py = abs((mez_diam[1][1] + mez_diam[2][1]) *1000)

print(int(Px), int(Py))

Приведём решение на языке Python для файла Б.

from math import dist

data = []

for s in open('27b.txt'):

x, y = [float(d) for d in s.replace(',', '.').split()]

data.append([x, y])

rast = 3

clusters = []

while data:

cl = [data.pop()]

for p in cl:

sosed = [p1 for p1 in data if dist(p, p1) < rast]

for p1 in sosed:

cl.append(p1)

data.remove(p1)

if len(cl) >= 2:

clusters.append(cl)

clusters.sort(key=len)

#print(*[len(cl) for cl in clusters]) # - проверяет кол-во кластеров

# 2 кластера для файла A и 3 для файла B

# В случае противоречия меняем rast - это значение

def rast_clast(cluster1, cluster2):

res = []

for s1 in cluster1:

for s2 in cluster2:

res.append([dist(s1,s2), s1, s2])

return max(res)

mez_diam = [rast_clast(clusters[i], clusters[j]) for i in range(len(clusters)) for j in range(i+1, len(clusters))]

Q1 = sum(d[0] for d in mez_diam) *100

Q2 = max(dist(i,[1,1]) for d in mez_diam for i in d[1:]) * 100

print(int(Q1),int(Q2))

Ответ: 21549 1946 7140 2018.

№ п/п	№ задания	Ответ
1	87418	21549 1946 7140 2018

Ключ