Задание 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 аналогична файлу А.
Для каждого файла определите плотность каждого кластера, затем вычислите два числа: $P_{min}$ – минимальная плотность кластера, и $P_{avg}$ – среднее арифметическое плотности кластеров.
В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_{min} * 100 000$, затем целую часть произведения $P_{avg} * 100 000$ для файла А, во второй строке – аналогичные данные для файла В.
Возможные данные одного из файлов проиллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов.
Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/20295_27A.txt
Файл В к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/20295_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 plot(cl):

m = []

for p in cl:

k = len([p1 for p1 in cl if dist(p,p1)<=1])

m.append(k)

return sum(m)/len(m)

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

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

print(int(min(da)*100_000), int(sum(da)/len(da)*100_000))

print(int(min(db)*100_000), int(sum(db)/len(db)*100_000))

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

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