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