Карточки
Тесты
Главная
Курсы
Подписка
27. Программирование: #298879
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной $H$ и $W$, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
В ответе запишите четыре числа через запятую: сначала абсолютную величину целой части произведения $P_x \times 10,000$, затем абсолютную величину целой части произведения $P_y \times 10,000$; сначала абсолютную величину целой части произведения $Q_x \times 10,000$, затем абсолютную величину целой части произведения $Q_y \times 10,000$.
Возможные данные одного из файлов проиллюстрированы графиком. Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла.
Прямоугольники не пересекаются, значит, кластеры разделены в пространстве, и никакого хитрого алгоритма не требуется — нужно лишь найти «щели» между сгустками точек. Определение центра здесь геометрическое: это точка самого кластера (а не произвольная точка плоскости), для которой сумма расстояний до остальных минимальна. Поэтому её ищут перебором по точкам кластера, а не считают как среднее арифметическое координат — это самая частая ошибка в этом задании.
Файл $А$. Первая строка — заголовок $X$ $Y$, данных $207$ точек. Разброс ординат сразу выдаёт структуру: один кластер лежит в полосе $y \in [5{,}64;\ 7{,}97]$, второй — в полосе $y \in [18{,}10;\ 20{,}91]$. Между ними огромный пустой промежуток, поэтому достаточно разделить точки условием $y < 12$. По абсциссам кластеры почти совпадают ($x \in [2{,}84;\ 4{,}34]$ и $x \in [4{,}07;\ 5{,}95]$), так что делить по $x$ было бы ошибкой. Размеры групп $77$ и $130$ точек, обе укладываются в прямоугольник $6 \times 4{,}5$ — проверка сходится.
Файл $Б$. Здесь глазами полосу уже не выделить: кластеры разнесены и по $x$, и по $y$. Надёжнее разбить точки на компоненты связности — объединять точки, отстоящие друг от друга меньше чем на $1$. Внутри плотного сгустка соседи всегда ближе этого порога, а между кластерами расстояние заведомо больше, поскольку прямоугольники не пересекаются. Такой проход даёт группы размерами $397$, $133$, $74$ и три одиночные точки — это и есть три аномалии, о которых говорится в условии; они отбрасываются автоматически, потому что состоят из одной точки. Кластер с минимальным количеством точек — тот, где их $74$, с максимальным — где $397$.
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))
# файл А: два кластера разделены щелью по ординате
A = load('27-01_A.xlsx')
a1 = [p for p in A if p[1] < 12]
a2 = [p for p in A if p[1] >= 12]
c1, c2 = center(a1), center(a2)
Px, Py = (c1[0] + c2[0]) / 2, (c1[1] + c2[1]) / 2
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
# файл Б: компоненты связности, одиночки — аномалии
def clusters(pts, eps=1.0):
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
B = load('27-01_B.xlsx')
cs = sorted((c for c in clusters(B) if len(c) > 3), key=len)
b1, b2 = center(cs[0]), center(cs[-1])
Qx, Qy = b1[0] + b2[0], b1[1] + b2[1]
print(abs(int(Qx * 10000)), abs(int(Qy * 10000)))
Результаты для файла $А$. Центры кластеров: $(3{,}5602193;\ 6{,}8574664)$ и $(4{,}9372174;\ 19{,}5388034)$. Отсюда $P_x = (3{,}5602193 + 4{,}9372174) / 2 = 4{,}24871835$ и $P_y = (6{,}8574664 + 19{,}5388034) / 2 = 13{,}1981349$. После умножения на $10,000$ и отбрасывания дробной части получаем $42487$ и $131981$.
Результаты для файла $Б$. Всего $607$ точек, из них три аномальные. Центр самого маленького кластера ($74$ точки) — $(16{,}9328755;\ 22{,}607628)$, центр самого большого ($397$ точек) — $(10{,}1344184;\ 13{,}5931472)$. Складываем координаты: $Q_x = 16{,}9328755 + 10{,}1344184 = 27{,}0672939$ и $Q_y = 22{,}607628 + 13{,}5931472 = 36{,}2007752$, что даёт $270672$ и $362007$.
20
