Карточки
Тесты
Главная
Курсы
Подписка
27. Программирование: #298980
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной $H$ и $W$, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
В ответе запишите четыре числа через запятую: сначала целую часть абсолютного значения произведения $P_1 \times 10,000$, затем целую часть абсолютного значения произведения $P_2 \times 10,000$; сначала целую часть абсолютного значения произведения $Q_x \times 10,000$, затем целую часть абсолютного значения произведения $Q_y \times 10,000$.
Возможные данные одного из файлов иллюстрированы графиком.
Обратите внимание на формулировку для файла $Б$: сравниваются расстояния центров до начала координат, то есть величины $\sqrt{x^2 + y^2}$, но в ответ идёт не расстояние, а координата — абсцисса самого далёкого центра и ордината самого близкого. Это два разных кластера, и путать их нельзя.
Центр здесь определяется через сумму расстояний (а не через минимакс, как в «лабораторных» задачах) — это точка самого кластера, ищем её перебором.
Кластеризация. Прямоугольники не пересекаются, поэтому кластеры разделены в пространстве. Разбиваем точки на компоненты связности, но порог нужен больше обычного: точек мало ($211$ и $505$), сгустки разрежены, и при пороге $0{,}5$ данные рассыпаются на десятки кусков. Устойчивый результат в файле $А$ начинается с $1{,}0$, в файле $Б$ — с $0{,}8$. Проверяем: число кластеров совпадает с условием, и каждый укладывается в прямоугольник заданного размера — например, кластеры файла $А$ занимают около $5{,}7$ по одной стороне и $3{,}7$ по другой при допустимых $8$ и $4$.
Три одиночные точки в файле $Б$ — это обещанные аномалии; они отсеиваются автоматически по размеру компоненты. Проверка: ближайший сосед у них удалён на $12$–$45$ единиц, тогда как внутри кластеров точки идут вплотную.
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
A = load('27-18_A.ods')
ca = clusters(A)
sm, bg = center(min(ca, key=len)), center(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-18_B.ods') # одиночки отсеиваются как аномалии
cen = [center(c) for c in clusters(B) if len(c) > 3]
far = max(cen, key=lambda c: math.hypot(*c))
near = min(cen, 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]$, его центр — $(19{,}461133;\ 97{,}650624)$; больший занимает $x \in [63{,}94;\ 69{,}70]$, $y \in [84{,}54;\ 87{,}84]$ с центром $(67{,}330505;\ 86{,}247527)$. Отсюда $P_1 = 19{,}461133 + 97{,}650624 = 117{,}1117564$ и $P_2 = 67{,}330505 + 86{,}247527 = 153{,}5780321$, что после умножения на $10,000$ и отбрасывания дробной части даёт $1171117$ и $1535780$.
Результаты для файла $Б$. Всего $505$ точек: три кластера по $177$, $167$ и $158$ точек плюс три аномалии. Центры кластеров — $(23{,}822967;\ 37{,}122155)$, $(22{,}223846;\ 45{,}924376)$ и $(25{,}701352;\ 28{,}083771)$, их расстояния до начала координат равны $44{,}108821$, $51{,}019091$ и $38{,}069117$.
Самый далёкий центр — $(22{,}223846;\ 45{,}924376)$, его абсцисса $Q_x = 22{,}223846$. Самый близкий — $(25{,}701352;\ 28{,}083771)$, его ордината $Q_y = 28{,}083771$. Умножаем на $10,000$ и берём целые части: $222238$ и $280837$.
Обратите внимание, что у самого далёкого центра абсцисса как раз наименьшая из трёх — удалённость определяется обеими координатами сразу, и брать «крайний по $x$» нельзя.
20
