Карточки
Тесты
Главная
Курсы
Подписка
27. Программирование: #299520
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри квадрата со стороной длиной $H$, причём эти квадраты между собой не пересекаются. Стороны квадрата не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров квадрата.
В ответе запишите четыре числа через запятую: сначала целую часть произведения $|P_x| \times 10,000$, затем целую часть произведения $|P_y| \times 10,000$ для файла $А$, далее — аналогичные данные для файла $Б$.
Возможные данные одного из файлов иллюстрированы графиком. Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла.
Центр определяется через сумму расстояний — это точка самого кластера, ищем её перебором, а не как среднее арифметическое координат. А вот $P_x$ и $P_y$ — уже обычные средние арифметические, но не по всем точкам, а только по найденным центрам.
Кластеризация. Квадраты не пересекаются, поэтому кластеры разделены в пространстве. Разбиваем точки на компоненты связности. Порог $0{,}3$ здесь мал — данные разрежены, и файлы рассыпаются на полтора десятка обрывков; начиная с $0{,}5$–$0{,}8$ результат устойчив вплоть до $2{,}0$. Берём $0{,}8$.
Проверяем допустимость: в файле $А$ группы занимают области примерно $3{,}2 \times 2{,}5$ и $3{,}5 \times 2{,}5$ — обе умещаются в квадрат со стороной $4{,}7$. В файле $Б$ области около $1{,}8 \times 1{,}6$, $2{,}5 \times 2{,}8$ и $0{,}7 \times 1{,}9$ при допустимой стороне $4$. Число кластеров совпадает с условием: два и три.
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=0.8):
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-29А.ods', '27-29Б.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))
Результаты для файла $А$. Всего $220$ точек, два кластера ровно по $110$ точек. Первый занимает область $x \in [4{,}27;\ 7{,}44]$, $y \in [23{,}07;\ 25{,}60]$, его центр — $(6{,}110722;\ 24{,}26957)$; второй занимает $x \in [2{,}23;\ 5{,}73]$, $y \in [4{,}69;\ 7{,}17]$ с центром $(3{,}830122;\ 5{,}815582)$. Отсюда $P_x = (6{,}110722 + 3{,}830122) / 2 = 4{,}970422$ и $P_y = (24{,}26957 + 5{,}815582) / 2 = 15{,}042576$, что после умножения на $10,000$ и отбрасывания дробной части даёт $49704$ и $150425$.
Результаты для файла $Б$. Всего $510$ точек, три кластера по $298$, $106$ и $106$ точек с центрами $(-1{,}66068;\ -4{,}56708)$, $(-8{,}18279;\ 3{,}849255)$ и $(-1{,}75482;\ 6{,}741675)$. Отсюда $P_x = -3{,}866096667$ и $P_y = 2{,}00795$, что даёт $38660$ и $20079$.
20
