Карточки
Тесты
Главная
Курсы
Подписка
27. Программирование: #298884
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной $H$ и $W$, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
В ответе запишите четыре числа через запятую: сначала абсолютную величину целой части произведения $P_x \times 10,000$, затем абсолютную величину целой части произведения $P_y \times 10,000$; сначала абсолютную величину целой части произведения $Q_1 \times 10,000$, затем абсолютную величину целой части произведения $Q_2 \times 10,000$.
Возможные данные одного из файлов проиллюстрированы графиком. Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла.
Прямоугольники не пересекаются, значит, кластеры разделены в пространстве, и хитрый алгоритм не нужен: достаточно найти «щели» между сгустками точек. Определение центра здесь геометрическое — это точка самого кластера (а не произвольная точка плоскости), для которой сумма расстояний до остальных минимальна. Ищем её перебором по точкам кластера, а не как среднее арифметическое координат: это самая частая ошибка в задании.
Универсальный способ разбиения — компоненты связности: объединяем точки, отстоящие друг от друга меньше чем на некоторый порог. Внутри плотного сгустка соседи всегда ближе порога, а между кластерами расстояние заведомо больше, поскольку прямоугольники не пересекаются. Порог нужно подбирать осмысленно и потом проверять результат: он должен дать ровно столько кластеров, сколько обещано в условии.
Файл $А$. Всего $217$ точек (первая строка — заголовок $X$ $Y$). Кластеры разнесены по ординате: один лежит в полосе $y \in [6{,}51;\ 10{,}42]$, второй — в полосе $y \in [22{,}63;\ 26{,}74]$, между ними пустота шириной больше $12$. Здесь важна тонкость: при пороге $1$ от нижнего кластера отрывается точка $(2{,}0197429;\ 6{,}5052367)$ — до ближайшего соседа у неё $1{,}03$. Но аномалий в файле $А$ по условию нет, а с этой точкой нижняя группа по-прежнему укладывается в прямоугольник ($3{,}65$ по $x$ и $3{,}91$ по $y$ против допустимых $4{,}5$ и $6$), так что точка принадлежит кластеру. Надёжнее просто разделить точки условием $y < 15$: получаются группы из $110$ и $107$ точек.
Файл $Б$. Здесь $617$ точек. Порог $1$ (или $1{,}5$) даёт группы размерами $419$, $107$, $88$ и три одиночные точки — это и есть обещанные аномалии. Проверка: у каждой из них ближайший сосед находится на расстоянии больше $23$, тогда как внутри любого кластера точки идут вплотную. Три настоящих кластера укладываются в прямоугольники нужного размера.
import openpyxl, math
from itertools import combinations
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-02_A.xlsx')
c1, c2 = center([p for p in A if p[1] < 15]), center([p for p in A if p[1] >= 15])
Px, Py = c1[0] + c2[0], c1[1] + c2[1]
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
# файл Б: компоненты связности, одиночки — аномалии
B = load('27-02_B.xlsx')
cs = [center(c) for c in clusters(B) if len(c) > 3]
d = [math.dist(a, b) for a, b in combinations(cs, 2)]
print(abs(int(min(d) * 10000)), abs(int(max(d) * 10000)))
Результаты для файла $А$. Центры кластеров: $(3{,}6319192;\ 8{,}782799)$ и $(6{,}1168889;\ 24{,}8122646)$. Отсюда $P_x = 3{,}6319192 + 6{,}1168889 = 9{,}7488081$ и $P_y = 8{,}782799 + 24{,}8122646 = 33{,}5950636$. После умножения на $10,000$ и отбрасывания дробной части получаем $97488$ и $335950$.
Результаты для файла $Б$. Центры трёх кластеров: $(5{,}5317089;\ 24{,}5603028)$ для кластера из $419$ точек, $(8{,}4227338;\ 34{,}3897427)$ для кластера из $107$ точек и $(15{,}4888704;\ 34{,}9117814)$ для кластера из $88$ точек. Три попарных расстояния между ними равны $7{,}0853942$, $10{,}2457754$ и $14{,}3630837$. Значит, $Q_1 = 7{,}0853942$ (между вторым и третьим центрами) и $Q_2 = 14{,}3630837$, что даёт $70853$ и $143630$.
20
