Карточки
Тесты
Главная
Курсы
Подписка
27. Программирование: #298915
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной $H$ и $W$, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
В ответе запишите четыре числа через запятую: сначала абсолютную величину целой части произведения $P_x \times 10,000$, затем абсолютную величину целой части произведения $P_y \times 10,000$; сначала абсолютную величину целой части произведения $Q_x \times 10,000$, затем абсолютную величину целой части произведения $Q_y \times 10,000$.
Возможные данные одного из файлов проиллюстрированы графиком. Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла.
Прямоугольники не пересекаются, значит, кластеры разделены в пространстве, и хитрый алгоритм не нужен: достаточно найти «щели» между сгустками точек. Определение центра здесь геометрическое — это точка самого кластера (а не произвольная точка плоскости), для которой сумма расстояний до остальных минимальна. Ищем её перебором по точкам кластера, а не как среднее арифметическое координат: это самая частая ошибка в задании. Заметьте разницу с формулировкой для $P_x$ и $P_y$ — там среднее арифметическое действительно нужно, но уже от найденных центров.
Универсальный способ разбиения — компоненты связности: объединяем точки, отстоящие друг от друга меньше чем на некоторый порог. Внутри плотного сгустка соседи всегда ближе порога, а между кластерами расстояние заведомо больше, поскольку прямоугольники не пересекаются. Порог проверяем по результату: он должен дать ровно столько кластеров, сколько обещано в условии, и каждый должен укладываться в прямоугольник заданного размера.
Файл $А$. Всего $209$ точек (первая строка — заголовок $X$ $Y$). Разбиение устойчиво к выбору порога от $1$ до $2$: группы из $137$ и $72$ точек. Первая занимает область $x \in [6{,}13;\ 7{,}99]$, $y \in [18{,}49;\ 21{,}67]$, вторая — $x \in [3{,}15;\ 4{,}64]$, $y \in [5{,}72;\ 8{,}60]$. Обе укладываются в прямоугольник $6 \times 4{,}5$. Аномалий в файле $А$ нет, лишних одиночных точек алгоритм не находит.
Файл $Б$. Здесь $609$ точек. Разбиение снова устойчиво: группы размерами $397$, $137$, $72$ и три одиночные точки — это и есть обещанные аномалии. Проверка: у каждой из них ближайший сосед находится на расстоянии больше $24$, тогда как внутри кластеров точки идут вплотную. Кластер с минимальным количеством точек — тот, где их $72$, с максимальным — где $397$; складываются координаты именно их центров, средний кластер из $137$ точек в ответ не входит.
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-06_A.xlsx')
cs = [center(c) for c in clusters(A) if len(c) > 3]
Px = sum(p[0] for p in cs) / len(cs)
Py = sum(p[1] for p in cs) / len(cs)
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
B = load('27-06_B.xlsx') # одиночки отсеиваются как аномалии
cl = sorted((c for c in clusters(B) if len(c) > 3), key=len)
c_min, c_max = center(cl[0]), center(cl[-1])
Qx, Qy = c_min[0] + c_max[0], c_min[1] + c_max[1]
print(abs(int(Qx * 10000)), abs(int(Qy * 10000)))
Результаты для файла $А$. Центры кластеров: $(7{,}1031803;\ 19{,}817861)$ и $(3{,}9558582;\ 7{,}556738)$. Отсюда $P_x = (7{,}1031803 + 3{,}9558582) / 2 = 5{,}52951925$ и $P_y = (19{,}817861 + 7{,}556738) / 2 = 13{,}6872995$. После умножения на $10,000$ и отбрасывания дробной части получаем $55295$ и $136872$.
Результаты для файла $Б$. Центры кластеров: $(25{,}3459999;\ 22{,}8268984)$ для кластера из $72$ точек, $(18{,}3161517;\ 26{,}2694763)$ для кластера из $137$ точек и $(6{,}5724924;\ 22{,}0374135)$ для кластера из $397$ точек. Складываем координаты центров самого маленького и самого большого кластеров: $Q_x = 25{,}3459999 + 6{,}5724924 = 31{,}9184923$ и $Q_y = 22{,}8268984 + 22{,}0374135 = 44{,}8643119$, что даёт $319184$ и $448643$.
20
