Карточки
Тесты
Главная
Курсы
Подписка
27. Программирование: #299512
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри квадрата со стороной длиной $H$, причём эти квадраты между собой не пересекаются. Стороны квадрата не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров квадрата.
В ответе запишите четыре числа через запятую: сначала целую часть произведения $|P_x| \times 10,000$, затем целую часть произведения $|P_y| \times 10,000$ для файла $А$, затем — аналогичные данные для файла $Б$.
Возможные данные одного из файлов иллюстрированы графиком. Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла.
Центр определяется через сумму расстояний — это точка самого кластера, ищем её перебором, а не как среднее арифметическое координат. А вот $P_x$ и $P_y$ — уже обычные средние арифметические, но не по всем точкам, а только по найденным центрам.
Кластеризация. Квадраты не пересекаются, поэтому кластеры разделены в пространстве. Разбиваем точки на компоненты связности. Порог $0{,}5$ здесь мал — от кластеров отрываются одиночки (в файле $А$ четыре точки, в файле $Б$ одна); начиная с $0{,}8$ и вплоть до $2{,}5$ результат устойчив. Берём $1{,}0$.
Проверяем допустимость: в файле $А$ группы занимают области примерно $2{,}7 \times 2{,}1$ и $3{,}1 \times 2{,}7$ — обе умещаются в квадрат со стороной $4{,}7$. В файле $Б$ области около $2{,}7 \times 2{,}4$, $2{,}2 \times 1{,}9$ и $1{,}5 \times 0{,}8$ при допустимой стороне $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-28А.ods', '27-28Б.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))
Результаты для файла $А$. Всего $219$ точек, два кластера по $145$ и $74$ точки. Первый занимает область $x \in [3{,}73;\ 6{,}82]$, $y \in [22{,}37;\ 25{,}05]$, его центр — $(4{,}97254;\ 23{,}55815)$; второй занимает $x \in [2{,}41;\ 5{,}13]$, $y \in [4{,}13;\ 6{,}27]$ с центром $(3{,}507478;\ 5{,}281454)$. Отсюда $P_x = (4{,}97254 + 3{,}507478) / 2 = 4{,}240009$ и $P_y = (23{,}55815 + 5{,}281454) / 2 = 14{,}419802$, что после умножения на $10,000$ и отбрасывания дробной части даёт $42400$ и $144198$.
Результаты для файла $Б$. Всего $513$ точек, три кластера по $296$, $143$ и $74$ точки с центрами $(-5{,}24456;\ -2{,}96574)$, $(-3{,}45431;\ 7{,}186733)$ и $(2{,}566376;\ 5{,}422321)$. Отсюда $P_x = -2{,}044164667$ и $P_y = 3{,}214438$, что даёт $20441$ и $32144$.
20
