№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').
Ответвпиши то, что вывела программа
Показать разбор
- Прочитай файл, заменив запятые на точки, и собери кластеры соседями: точка ближе порога t попадает в кластер. Центр это точка с наименьшей суммой расстояний до остальных.
- Порог подбирай отдельно для каждого файла: начни с t = 1, печатай размеры кластеров. Кластеров больше, чем в условии, увеличивай t, меньше, уменьшай. Бери t из середины диапазона, где число кластеров нужное и размеры похожи на настоящие кучки.
- Голубой субкарлик это h[0] == 'O' и h[2:] == 'VI'.
- Файл А: A1 это расстояние между центрами, A2 это наименьшее расстояние между голубыми субкарликами из разных кластеров.
- Файл Б: выбери центр, ближайший к началу координат, и посчитай голубых субкарликов в его кластере. Затем возьми самый дальний центр и посчитай голубых субкарликов не дальше 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)