Карточки
Тесты
Главная
Курсы
Подписка
27. Программирование: #298912
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной $H$ и $W$, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
В ответе запишите четыре числа через запятую: сначала абсолютную величину целой части произведения $P_x \times 10,000$, затем абсолютную величину целой части произведения $P_y \times 10,000$; сначала целую часть произведения $Q_1 \times 10,000$, затем целую часть произведения $Q_2 \times 10,000$.
Возможные данные одного из файлов проиллюстрированы графиком. Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла.
Обратите внимание: $P_x$ и $P_y$ здесь берутся независимо друг от друга — это минимум по абсциссам и минимум по ординатам, а не координаты одной и той же точки. В данном файле они случайно принадлежат одному центру, но полагаться на это нельзя.
Прямоугольники не пересекаются, значит, кластеры разделены в пространстве, и хитрый алгоритм не нужен: достаточно найти «щели» между сгустками точек. Определение центра здесь геометрическое — это точка самого кластера (а не произвольная точка плоскости), для которой сумма расстояний до остальных минимальна. Ищем её перебором по точкам кластера, а не как среднее арифметическое координат: это самая частая ошибка в задании.
Универсальный способ разбиения — компоненты связности: объединяем точки, отстоящие друг от друга меньше чем на некоторый порог. Внутри плотного сгустка соседи всегда ближе порога, а между кластерами расстояние заведомо больше, поскольку прямоугольники не пересекаются. Порог проверяем по результату: он должен дать ровно столько кластеров, сколько обещано в условии, и каждый должен укладываться в прямоугольник заданного размера.
Файл $А$. Всего $223$ точки (первая строка — заголовок $X$ $Y$). Разбиение устойчиво к выбору порога от $1$ до $2$: группы из $92$ и $131$ точки. Первая занимает область $x \in [5{,}47;\ 8{,}48]$, $y \in [11{,}46;\ 13{,}00]$, вторая — $x \in [2{,}09;\ 5{,}53]$, $y \in [5{,}29;\ 6{,}96]$. Обе укладываются в прямоугольник $6 \times 4{,}5$. Аномалий в файле $А$ нет, и лишних одиночных точек алгоритм не находит.
Файл $Б$. Здесь $623$ точки. Разбиение снова устойчиво: группы размерами $407$, $113$, $100$ и три одиночные точки — это и есть обещанные аномалии. Проверка: у каждой из них ближайший сосед находится на расстоянии больше $22$, тогда как внутри кластеров точки идут вплотную. Кластер с минимальным количеством точек — тот, где их $100$, с максимальным — где $407$; именно между их центрами и считается $Q_1$.
Для $Q_2$ нужно в каждом кластере найти самую далёкую от его центра точку и взять наибольшее из этих значений по всем кластерам. Здесь легко ошибиться и посчитать максимальное расстояние между любыми двумя точками кластера — в условии речь именно о расстоянии от центра.
import openpyxl, math
def load(name):
ws = openpyxl.load_workbook(name).active
return [(r[0], r[1]) for r in ws.iter_rows(min_row=2, values_only=True)
if r[0] is not None] # min_row=2 — пропускаем заголовок
def center(c):
return min(c, key=lambda a: sum(math.dist(a, b) for b in c))
def clusters(pts, eps=1.5):
unused, res = set(range(len(pts))), []
while unused:
i = unused.pop(); comp, stack = [i], [i]
while stack:
a = stack.pop()
for j in list(unused):
if math.dist(pts[a], pts[j]) < eps:
unused.discard(j); comp.append(j); stack.append(j)
res.append([pts[k] for k in comp])
return res
A = load('27-04_A.xlsx')
cs = [center(c) for c in clusters(A) if len(c) > 3]
Px, Py = min(p[0] for p in cs), min(p[1] for p in cs)
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
B = load('27-04_B.xlsx') # одиночки отсеиваются как аномалии
cl = sorted((c for c in clusters(B) if len(c) > 3), key=len)
cen = [center(c) for c in cl]
Q1 = math.dist(cen[0], cen[-1]) # min и max по количеству точек
Q2 = max(max(math.dist(cn, p) for p in c) for c, cn in zip(cl, cen))
print(int(Q1 * 10000), int(Q2 * 10000))
Результаты для файла $А$. Центры кластеров: $(7{,}0391548;\ 12{,}3587258)$ и $(3{,}8471735;\ 6{,}1225014)$. Минимальная абсцисса $P_x = 3{,}8471735$, минимальная ордината $P_y = 6{,}1225014$. После умножения на $10,000$ и отбрасывания дробной части получаем $38471$ и $61225$.
Результаты для файла $Б$. Центры кластеров: $(21{,}3946551;\ 24{,}7510816)$ для кластера из $100$ точек, $(14{,}6275088;\ 23{,}5024317)$ для кластера из $113$ точек и $(11{,}555522;\ 14{,}5042082)$ для кластера из $407$ точек. Расстояние между центрами самого маленького и самого большого кластеров $Q_1 = 14{,}2058775$. Максимальные удаления точек от своего центра по кластерам: $2{,}2357$, $2{,}3039$ и $2{,}5300$, наибольшее из них $Q_2 = 2{,}5299752$. Умножаем на $10,000$ и берём целые части: $142058$ и $25299$.
20
