Карточки
Тесты
Главная
Курсы
Подписка
27. Программирование: #299509
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри квадрата со стороной длиной $H$, причём эти квадраты между собой не пересекаются. Стороны квадрата не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров квадрата.
В ответе запишите четыре числа через запятую: сначала целую часть произведения $|P_x| \times 10,000$, затем целую часть произведения $|P_y| \times 10,000$ для файла $А$, далее — аналогичные данные для файла $Б$.
Возможные данные одного из файлов иллюстрированы графиком. Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла.
Центр определяется через сумму расстояний — это точка самого кластера, ищем её перебором, а не как среднее арифметическое координат. А вот $P_x$ и $P_y$ — уже обычные средние арифметические, но не по всем точкам, а только по найденным центрам.
Кластеризация. Квадраты не пересекаются, поэтому кластеры разделены в пространстве. Разбиваем точки на компоненты связности. Данные здесь удобные: результат не меняется при любом пороге от $0{,}5$ до $2{,}5$ в обоих файлах, так что берём $1{,}0$.
Проверяем допустимость: в файле $А$ группы занимают области примерно $3{,}2 \times 2{,}6$ и $2{,}6 \times 2{,}4$ — обе умещаются в квадрат со стороной $4{,}7$. В файле $Б$ области около $1{,}3 \times 1{,}3$, $3{,}1 \times 3{,}0$ и $1{,}7 \times 2{,}3$ при допустимой стороне $5$. Число кластеров совпадает с условием: два и три.
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
for name in ['27-27А.ods', '27-27В.ods']:
cs = [center(c) for c in clusters(load(name))]
Px = sum(p[0] for p in cs) / len(cs)
Py = sum(p[1] for p in cs) / len(cs)
print(int(abs(Px) * 10000), int(abs(Py) * 10000))
Результаты для файла $А$. Всего $218$ точек, два кластера по $146$ и $72$ точки. Первый занимает область $x \in [5{,}20;\ 8{,}44]$, $y \in [21{,}61;\ 24{,}22]$, его центр — $(7{,}034254;\ 23{,}01446)$; второй занимает $x \in [2{,}76;\ 5{,}35]$, $y \in [3{,}43;\ 5{,}80]$ с центром $(4{,}20046;\ 4{,}600608)$. Отсюда $P_x = (7{,}034254 + 4{,}20046) / 2 = 5{,}617357$ и $P_y = (23{,}01446 + 4{,}600608) / 2 = 13{,}807534$, что после умножения на $10,000$ и отбрасывания дробной части даёт $56173$ и $138075$.
Результаты для файла $Б$. Всего $518$ точек, три кластера по $300$, $146$ и $72$ точки с центрами $(-6{,}15735;\ -5{,}05153)$, $(-4{,}54276;\ 6{,}500928)$ и $(2{,}215176;\ 8{,}612747)$. Отсюда $P_x = -2{,}828311333$ и $P_y = 3{,}354048333$, что даёт $28283$ и $33540$.
20
