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

Оранжевые гиганты

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

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

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

Ответвпиши то, что вывела программа
Показать разбор
  1. Прочитай файл, заменив запятые на точки, и собери кластеры соседями: точка ближе порога t попадает в кластер. Центр это точка с наименьшей суммой расстояний до остальных.
  2. Порог подбирай отдельно для каждого файла: начни с t = 1, печатай размеры кластеров. Кластеров больше, чем в условии, увеличивай t, меньше, уменьшай. Бери t из середины диапазона, где число кластеров нужное и размеры похожи на настоящие кучки.
  3. Оранжевый гигант это h[0] == 'K' и h[2:] == 'III'.
  4. Файл А: A1 это наименьшее расстояние от такой звезды до центра её кластера, A2 это сумма расстояний от центров до точки (-1; -2).
  5. Файл Б: посчитай такие звёзды в каждом кластере, найди кластер с наименьшим числом и выведи модули координат его центра, умноженные на 10000.
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 good(p):
    return p[1][0] == 'K' and p[1][2:] == 'III'

clusters = load('task_31163_A.txt', 0.7)
c = [centroids(cl) for cl in clusters]
A1 = min(dist(p[0], c[i][0]) for i in range(2) for p in clusters[i] if good(p))
A2 = sum(dist(x[0], (-1, -2)) for x in c)
print(int(A1 * 10000), int(A2 * 10000))

clusters = load('task_31163_B.txt', 0.7)
c = [centroids(cl) for cl in clusters]
counts = [sum(1 for p in cl if good(p)) for cl in clusters]
i = counts.index(min(counts))
print(int(abs(c[i][0][0]) * 10000), int(abs(c[i][0][1]) * 10000))