ЗАДАНИЯ №27 С ДВ И ПЕРВОГО ДНЯ СОВПАДАЮТ
Кластеры — прямоугольники H на W. Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по обычной формуле с корнем.
В файле A хранятся данные о звёздах двух кластеров. В файле B хранятся данные о звёздах трёх кластеров. Также в файле B присутствуют точки, являющиеся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.
Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px - максимальную из абсцисс центров кластеров, и Py - максимальную из ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Qx - разность абсцисс центров кластеров с минимальным и максимальным количеством точек, и Qy - разность ординат центров кластеров с минимальным и максимальным количеством точек. Гарантируется, что во всех кластерах количество точек различно.
В ответе запишите четыре числа: в первой строке - сначала целую часть абсолютного значения произведения Px × 10000, затем целую часть абсолютного значения произведения Py × 10 000; во второй строке - сначала целую часть абсолютного значения произведения Qx × 10 000, затем целую часть абсолютного значения произведения Qy × 10 000.
Решение файл А
Разделяем точки на кластеры с помощью таблиц (картинка 1). Используем прямую х = 5.
from math import dist
def get_centroid(cluster):
res = []
for star in cluster:
res.append([sum(dist(star, point) for point in cluster), star])
return min(res)[1]
file = open('27A.txt')
file.readline()
clusters = [[] for i in range(2)]
for line in file:
x, y = map(float, line.replace(',', '.').split())
if x < 5:
clusters[0].append([x, y])
else:
clusters[1].append([x, y])
centroids = [get_centroid(cluster) for cluster in clusters]
px = int(abs(max(x for x, y in centroids) * 10000) // 1)
py = int(abs(max(y for x, y in centroids) * 10000) // 1)
print(px, py)
Решение файл Б
Разделим кластеры также с помощью таблиц. Чтобы исключить аномалии заметим, что все кластеры попадают в прямоугольник, где 0 < x < 15 и 0 < y < 30, а аномалии нет, поэтому в первую очередь проверим это условие. Нижний кластер отделяем прямой у = 10, а между двумя верхними проводим наклонную: н = -х + 30.
from math import dist
def get_centroid(cluster):
res = []
for star in cluster:
res.append([sum(dist(star, point) for point in cluster), star])
return min(res)[1]
file = open('27B.txt')
file.readline()
clusters = [[] for i in range(3)]
for line in file:
x, y = map(float, line.replace(',', '.').split())
if 0 < x < 15 and 0 < y < 30:
if y < 10:
clusters[0].append([x, y])
elif y > -x + 30:
clusters[1].append([x, y])
else:
clusters[2].append([x, y])
clusters.sort(key=len)
centroids = [get_centroid(cluster) for cluster in clusters]
qx = int(abs((centroids[0][0] - centroids[-1][0]) * 10000) // 1)
qy = int(abs((centroids[0][1] - centroids[-1][1]) * 10000) // 1)
print(qx, qy)
#информатика
