Карточки
Тесты
Главная
Курсы
Подписка
27. Программирование: #298979
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной $H$ и $W$, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
В ответе запишите четыре числа через запятую: сначала целую часть абсолютной величины произведения $P_1 \times 10,000$, затем целую часть абсолютной величины произведения $P_2 \times 10,000$; сначала целую часть произведения $Q_x \times 10,000$, затем целую часть произведения $Q_y \times 10,000$.
Возможные данные одного из файлов проиллюстрированы графиком.
Главное отличие от привычных задач: здесь ищется антицентр — точка кластера с максимальной суммой расстояний до остальных. Это всегда точка на краю сгустка, а не в его середине. Технически меняется одна строчка: вместо min берём max по той же сумме.
Второе, на что стоит смотреть внимательно: для файла $Б$ сравниваются расстояния антицентров до начала координат, то есть величины $\sqrt{x^2 + y^2}$, но в ответ идёт не расстояние, а координата — абсцисса самого далёкого антицентра и ордината самого близкого. Это два разных кластера.
Кластеризация. Прямоугольники не пересекаются, поэтому кластеры разделены в пространстве. Разбиваем точки на компоненты связности, но порог нужен больше обычного: точек мало ($211$ и $505$), сгустки разрежены, и при пороге $0{,}5$ данные рассыпаются на десятки кусков. Устойчивый результат в файле $А$ начинается с $1{,}0$, в файле $Б$ — с $0{,}8$. Проверяем: число кластеров совпадает с условием, и каждый укладывается в прямоугольник заданного размера — например, кластеры файла $А$ занимают около $5{,}7$ по одной стороне и $3{,}7$ по другой при допустимых $8$ и $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 anticenter(c): # максимум суммы расстояний
return max(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
A = load('27-19_A.ods')
ca = clusters(A)
sm, bg = anticenter(min(ca, key=len)), anticenter(max(ca, key=len))
P1, P2 = sm[0] + sm[1], bg[0] + bg[1]
print(int(abs(P1 * 10000)), int(abs(P2 * 10000)))
B = load('27-19_B.ods') # одиночки отсеиваются как аномалии
ac = [anticenter(c) for c in clusters(B) if len(c) > 3]
far = max(ac, key=lambda c: math.hypot(*c))
near = min(ac, key=lambda c: math.hypot(*c))
print(int(abs(far[0] * 10000)), int(abs(near[1] * 10000)))
Результаты для файла $А$. Всего $211$ точек, кластеры содержат $100$ и $111$ точек. Меньший занимает область $x \in [16{,}87;\ 22{,}53]$, $y \in [95{,}44;\ 99{,}14]$, его антицентр — $(16{,}998415;\ 95{,}672752)$; больший занимает $x \in [63{,}94;\ 69{,}70]$, $y \in [84{,}54;\ 87{,}84]$ с антицентром $(63{,}940626;\ 87{,}777510)$. Оба лежат у самого края своих сгустков, как и должно быть. Отсюда $P_1 = 16{,}998415 + 95{,}672752 = 112{,}6711664$ и $P_2 = 63{,}940626 + 87{,}777510 = 151{,}7181367$, что после умножения на $10,000$ и отбрасывания дробной части даёт $1126711$ и $1517181$.
Результаты для файла $Б$. Всего $505$ точек: три кластера по $177$, $167$ и $158$ точек плюс три аномалии. Антицентры кластеров — $(22{,}170759;\ 39{,}658913)$, $(20{,}526123;\ 43{,}733457)$ и $(28{,}463219;\ 28{,}234534)$, их расстояния до начала координат равны $45{,}435360$, $48{,}310837$ и $40{,}091692$.
Самый далёкий антицентр — $(20{,}526123;\ 43{,}733457)$, его абсцисса $Q_x = 20{,}526123$. Самый близкий — $(28{,}463219;\ 28{,}234534)$, его ордината $Q_y = 28{,}234534$. Умножаем на $10,000$ и берём целые части: $205261$ и $282345$.
Обратите внимание, что у самого далёкого антицентра абсцисса как раз наименьшая из трёх — удалённость определяется обеими координатами сразу, и брать «крайний по $x$» нельзя.
20
