Карточки
Тесты
Главная
Курсы
Подписка
27. Программирование: #299501
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри квадрата со стороной длиной $H$, причём эти квадраты между собой не пересекаются. Стороны квадрата не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров квадрата.
В ответе запишите четыре числа через запятую: сначала целую часть произведения $|P_x| \times 10,000$, затем целую часть произведения $|P_y| \times 10,000$ для файла $А$, далее — аналогичные данные для файла $Б$.
Возможные данные одного из файлов иллюстрированы графиком. Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла.
Центр определяется через сумму расстояний — это точка самого кластера, ищем её перебором, а не как среднее арифметическое координат. А вот $P_x$ и $P_y$ — уже обычные средние арифметические, но не по всем точкам, а только по найденным центрам.
Кластеризация. Квадраты не пересекаются, поэтому кластеры разделены в пространстве. Разбиваем точки на компоненты связности. Здесь данные удобные: в файле $А$ результат устойчив начиная с $0{,}8$ (при $0{,}5$ отрываются две одиночки), в файле $Б$ — при любом пороге от $0{,}5$ до $2{,}5$. Берём $1{,}0$.
Проверяем допустимость: в файле $А$ группы занимают области примерно $3{,}2 \times 2{,}6$ и $3{,}5 \times 2{,}0$ — обе умещаются в квадрат со стороной $4{,}7$. В файле $Б$ области около $2{,}7 \times 2{,}3$, $2{,}0 \times 1{,}8$ и $0{,}9 \times 1{,}2$ при допустимой стороне $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-26А.ods', '27-26В.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))
Результаты для файла $А$. Всего $213$ точек, два кластера по $110$ и $103$ точки. Первый занимает область $x \in [2{,}23;\ 5{,}42]$, $y \in [5{,}53;\ 8{,}12]$, его центр — $(3{,}880166;\ 7{,}007236)$; второй занимает $x \in [4{,}31;\ 7{,}80]$, $y \in [24{,}35;\ 26{,}30]$ с центром $(5{,}982654;\ 25{,}47965)$. Отсюда $P_x = (3{,}880166 + 5{,}982654) / 2 = 4{,}93141$ и $P_y = (7{,}007236 + 25{,}47965) / 2 = 16{,}243443$, что после умножения на $10,000$ и отбрасывания дробной части даёт $49314$ и $162434$.
Результаты для файла $Б$. Всего $517$ точек, три кластера по $300$, $110$ и $107$ точек с центрами $(-5{,}37374;\ -2{,}54324)$, $(4{,}49194;\ 7{,}842857)$ и $(-2{,}72761;\ 7{,}452484)$. Отсюда $P_x = -1{,}203136667$ и $P_y = 4{,}250700333$, что даёт $12031$ и $42507$.
20
