Задание 27 ЕГЭ по информатике

Question

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной $H$ и $W$, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Средним расстоянием назовём среднее арифметическое расстояние между всеми парами различных точек в кластере. Расстояние между двумя точками на плоскости $A(x_1, y_1)$ и $B(x_2, y_2)$ вычисляется по формуле:
$\textit{d}(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.
В файле A хранятся данные о звёздах четырёх кластеров, где $H=3$, $W=3$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле B хранятся данные о звёздах семи кластеров, где $H=5$, $W=5$ для каждого кластера. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле B аналогична файлу А.
Для каждого файла определите среднее расстояние в каждом кластере, затем вычислите два числа: $S_{min}$ – минимальное среднее расстояние кластера, и $S_{max}$ – максимальное среднее расстояние кластера.
В ответе запишите четыре числа: в первой строке сначала целую часть произведения $S_{min} * 100 000$, затем целую часть произведения $S_{max} * 100 000$ для файла А, во второй строке – аналогичные данные для файла В.
Возможные данные одного из файлов проиллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов.
Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/20292_27A.txt
Файл В к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/20292_27B.txt

Accepted Answer

clustersA = [[] for i in range(4)]

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

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

if x<0 and y>0:

clustersA[0].append([x,y])

if x<2 and y<0:

clustersA[1].append([x,y])

if x>2 and y>2:

clustersA[2].append([x,y])

if x>3 and y<1.5:

clustersA[3].append([x,y])

#print([len(cl) for cl in clustersA])

clustersB = [[] for i in range(7)]

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

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

if x>6 and y>3:

clustersB[0].append([x,y])

elif x>1 and y>1:

clustersB[1].append([x,y])

elif x>6:

clustersB[2].append([x,y])

elif x>1:

clustersB[3].append([x,y])

elif y<-4:

clustersB[4].append([x,y])

elif x<-4:

clustersB[5].append([x,y])

else:

clustersB[6].append([x,y])

#print([len(cl) for cl in clustersB])

from math import dist

def Savg(cl):

s = k = 0

for p in cl:

for p1 in cl:

if p!=p1:

s += dist(p,p1)

k += 1

return s/k

da = [Savg(cl) for cl in clustersA]

db = [Savg(cl) for cl in clustersB]

print(int(min(da)*100_000), int(max(da)*100_000))

print(int(min(db)*100_000), int(max(db)*100_000))

Задание 27 ЕГЭ по информатике

Кластеризация