Карточки
Тесты
Главная
Курсы
Подписка
27. Программирование: #299485
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров) так, что они будут лежать внутри сектора окружности радиуса $R = 50$ с центральным углом $20°$.
В ответе запишите четыре числа через запятую: сначала целую часть произведения $|P_x| \times 10,000$, затем целую часть произведения $|P_y| \times 10,000$ для файла $А$, аналогичные данные для файла $Б$.
Возможные данные одного из файлов иллюстрированы графиком. Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемых файлов.
Здесь кластеры устроены совсем не так, как в предыдущих задачах: это не круглые сгустки, а вытянутые лучи, расходящиеся из общей точки $C$ (график с «веером» лучей это и показывает). Привычная кластеризация по связности здесь работать не будет: возле точки $C$ лучи сходятся почти вплотную, а на дальнем конце соседние точки одного луча могут отстоять друг от друга дальше, чем точки разных лучей у основания.
Ключевая идея. Сектор — это диапазон углов. Значит, надо перейти к полярным координатам с полюсом в точке $C$: для каждой звезды считаем угол $\varphi = \operatorname{atan2}(y — y_C,\ x — x_C)$, переводим в градусы и приводим к диапазону $[0; 360)$. Точки одного кластера дают близкие углы, точки разных кластеров разделены заметными пустыми промежутками.
Дальше сортируем точки по углу и разрезаем список там, где разрыв больше порога (я взял $5°$: реальные промежутки между кластерами составляют $11°$–$14°$, а внутри кластера соседние углы отличаются на доли градуса). Отдельно надо обработать «склейку через ноль»: если первая и последняя группы примыкают друг к другу через $360°$, их нужно объединить. В обоих файлах такой кластер как раз есть.
Проверка допустимости: угловая ширина каждой найденной группы должна укладываться в $20°$, а расстояние от $C$ до самой дальней точки — в $R = 50$. Здесь ширины получаются от $0$ до $13{,}3°$, максимальное удаление $36{,}1$ — всё сходится, и число кластеров совпадает с условием.
Центр — точка самого кластера с минимальной суммой расстояний до остальных, ищем перебором.
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 sectors(P, C, gap=5):
ang = lambda p: math.degrees(math.atan2(p[1] - C[1], p[0] - C[0])) % 360
pts = sorted(P, key=ang)
cl = [[pts[0]]]
for i in range(1, len(pts)):
if ang(pts[i]) - ang(pts[i - 1]) > gap:
cl.append([])
cl[-1].append(pts[i])
if len(cl) > 1 and ang(pts[0]) + 360 - ang(pts[-1]) <= gap:
cl[0] = cl.pop() + cl[0] # склейка кластера через 0°
return cl
for name, C in [('27-22_А.ods', (5, -9)), ('27-22_Б.ods', (-10, -7))]:
cs = [center(c) for c in sectors(load(name), C)]
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))
Результаты для файла $А$. Всего $99$ звёзд, ровно три кластера по $33$ точки. Их центры: $(22{,}9195807;\ -8{,}640175388)$, $(20{,}80248901;\ 2{,}526363421)$ и $(9{,}904454731;\ 5{,}244811718)$. Отсюда $P_x = 17{,}875508147$ и $P_y = -0{,}289666750$. Умножаем модули на $10,000$ и берём целые части: $178755$ и $2896$.
Результаты для файла $Б$. Всего $9908$ звёзд, ровно шесть кластеров: $1639$, $1644$, $1636$, $1662$, $1664$ и $1663$ точки. Их центры: $(7{,}959850343;\ -6{,}998475086)$, $(6{,}455732378;\ 0{,}719868963)$, $(1{,}912807864;\ 7{,}114680042)$, $(-5{,}241732947;\ 10{,}6777187)$, $(-13{,}1400515;\ 11{,}09127405)$ и $(-20{,}45236536;\ 7{,}925721859)$. Отсюда $P_x = -3{,}750959870$ и $P_y = 5{,}088464755$, что даёт $37509$ и $50884$.
20
