Все задачи №27
№27

Центры, голубые субкарлики

Звёзды на плоскости; кластеры — по прямоугольникам H×W; центр кластера — точка с минимальной суммой расстояний до остальных. Файл А — два кластера, файл Б — три. H=1,1, W=4,1. А: A1 — расстояние между центрами, A2 — наименьшее расстояние между голубыми субкарликами разных кластеров. Б: B1 — число голубых субкарликов в кластере, центр которого ближе всего к началу координат, B2 — число голубых субкарликов не дальше 0,9 от центра самого далёкого кластера. Ответ: A1·10000, A2·10000; B1, B2.

Источник: ФИПИ, № 31371

Скачать файл: task_31371_A.txt, task_31371_B.txt. В редакторе он уже лежит рядом с кодом, открывай как на экзамене: open('task_31371_A.txt').

Ответвпиши то, что вывела программа
Показать разбор
  1. Прочитай файл, заменив запятые на точки, и собери кластеры соседями: точка ближе порога t попадает в кластер. Центр это точка с наименьшей суммой расстояний до остальных.
  2. Порог подбирай отдельно для каждого файла: начни с t = 1, печатай размеры кластеров. Кластеров больше, чем в условии, увеличивай t, меньше, уменьшай. Бери t из середины диапазона, где число кластеров нужное и размеры похожи на настоящие кучки.
  3. Голубой субкарлик это h[0] == 'O' и h[2:] == 'VI'.
  4. Файл А: A1 это расстояние между центрами, A2 это наименьшее расстояние между голубыми субкарликами из разных кластеров.
  5. Файл Б: выбери центр, ближайший к началу координат, и посчитай голубых субкарликов в его кластере. Затем возьми самый дальний центр и посчитай голубых субкарликов не дальше 0,9 от него.
from math import dist

def load(name, t):
    data = []
    for line in open(name):
        x, y, h = line.replace(',', '.').split()
        data.append(([float(x), float(y)], h))
    clusters = []
    while data:
        clusters.append([data.pop(0)])
        for p in clusters[-1]:
            sosedi = [p1 for p1 in data if dist(p[0], p1[0]) < t]
            clusters[-1].extend(sosedi)
            for p1 in sosedi:
                data.remove(p1)
    return clusters

def centroids(cl):
    m = []
    for p in cl:
        sm = sum(dist(p[0], p1[0]) for p1 in cl)
        m.append([sm, p])
    return min(m)[1]

def blue(p):
    return p[1][0] == 'O' and p[1][2:] == 'VI'

clusters = load('task_31371_A.txt', 0.6)
c = [centroids(cl) for cl in clusters]
A1 = dist(c[0][0], c[1][0])
A2 = min(dist(a[0], b[0]) for a in clusters[0] if blue(a) for b in clusters[1] if blue(b))
print(int(A1 * 10000), int(A2 * 10000))

clusters = load('task_31371_B.txt', 1)
c = [centroids(cl) for cl in clusters]
d = [dist(p[0], (0, 0)) for p in c]
near = d.index(min(d))
far = d.index(max(d))
B1 = sum(1 for p in clusters[near] if blue(p))
B2 = sum(1 for p in clusters[far] if blue(p) and dist(p[0], c[far][0]) <= 0.9)
print(B1, B2)