Карточки
Тесты
Главная
Курсы
Подписка
27. Программирование: #298988
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $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$ берутся независимо друг от друга — это минимум по абсциссам и минимум по ординатам, а не координаты одной и той же точки. В данном файле они случайно принадлежат одному центру, но полагаться на это нельзя.
Центр здесь определяется через сумму расстояний — это точка самого кластера, ищем её перебором, а не как среднее арифметическое координат.
Кластеризация. Прямоугольники не пересекаются, поэтому кластеры разделены в пространстве. Разбиваем точки на компоненты связности. В файле $А$ результат устойчив при любом пороге от $0{,}5$ до $2$: две группы по $92$ и $131$ точке. В файле $Б$ порог $0{,}5$ мал — от кластеров отрываются лишние одиночки; начиная с $1{,}0$ остаются ровно три группы ($392$, $111$, $96$) и три одиночные точки, то есть обещанные аномалии. Проверяем размеры: каждый кластер укладывается в прямоугольник заданного размера.
Для $Q_2$ нужно в каждом кластере найти самую далёкую от его центра точку и взять наибольшее из этих значений по всем кластерам. Здесь легко ошибиться и посчитать наибольшее расстояние между любыми двумя точками кластера — в условии речь именно о расстоянии от центра.
import zipfile, math
from xml.etree import ElementTree as ET
T = '{urn:oasis:names:tc:opendocument:xmlns:table:1.0}'
O = '{urn:oasis:names:tc:opendocument:xmlns:office:1.0}'
def load(name):
x = ET.fromstring(zipfile.ZipFile(name).read('content.xml'))
P = []
for r in x.iter(T + 'table-row'):
parts = []
for c in r.iter(T + 'table-cell'):
v = c.get(O + 'value') or ''.join(c.itertext()).strip()
if v: parts.append(v)
tok = ' '.join(parts).replace(',', '.').split()
if len(tok) < 2: continue
try: P.append((float(tok[0]), float(tok[1])))
except ValueError: pass
return P
def center(c):
return min(c, key=lambda a: sum(math.dist(a, b) for b in c))
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
A = load('27-20_A.ods')
cs = [center(c) for c in clusters(A)]
Px, Py = min(p[0] for p in cs), min(p[1] for p in cs)
print(int(abs(Px * 10000)), int(abs(Py * 10000)))
B = load('27-20_B.ods') # одиночки отсеиваются как аномалии
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))
Результаты для файла $А$. Всего $223$ точки, кластеры содержат $92$ и $131$ точку. Первый занимает область $x \in [5{,}47;\ 8{,}48]$, $y \in [11{,}46;\ 13{,}00]$ с центром $(7{,}0391548;\ 12{,}3587258)$, второй — $x \in [2{,}09;\ 5{,}53]$, $y \in [5{,}29;\ 6{,}96]$ с центром $(3{,}8471735;\ 6{,}1225014)$. Минимальная абсцисса $P_x = 3{,}8471735$, минимальная ордината $P_y = 6{,}1225014$, что после умножения на $10,000$ и отбрасывания дробной части даёт $38471$ и $61225$.
Результаты для файла $Б$. Всего $602$ точки: три кластера по $392$, $111$ и $96$ точек плюс три аномалии. Центры кластеров — $(11{,}555522;\ 14{,}5042082)$ для кластера из $392$ точек, $(14{,}6275088;\ 23{,}5024317)$ для кластера из $111$ точек и $(21{,}3946551;\ 24{,}7510816)$ для кластера из $96$ точек. Расстояние между центрами самого маленького и самого большого кластеров $Q_1 = 14{,}2058775$.
Максимальные удаления точек от своего центра по кластерам равны $2{,}529975$, $2{,}303851$ и $2{,}235668$, наибольшее из них $Q_2 = 2{,}5299752$. Умножаем на $10,000$ и берём целые части: $142058$ и $25299$.
20
