27011.py

"""
ФИПИ: Задание 27. Анализ данных. Кластеризация

Фрагмент звёздного неба спроецирован на плоскость 
с декартовой системой координат. 
Учёный решил провести кластеризацию полученных точек, 
являющихся изображениями звёзд, то есть разбить их множество 
на N непересекающихся непустых подмножеств (кластеров), 
таких что точки каждого подмножества лежат внутри 
прямоугольника со сторонами длиной H и W, причём 
эти прямоугольники между собой не пересекаются. 
Стороны прямоугольников не обязательно параллельны координатным осям.

Гарантируется, что такое разбиение существует 
и единственно для заданных размеров прямоугольников.

Будем называть центром кластера точку в нём, 
сумма расстояний от которой до всех остальных 
точек кластера минимальна. 
У каждого кластера есть гарантированно единственный центр. 

Расстояние между двумя точками на плоскости 
A(x1,y1) и B(x2,y2) вычисляется по формуле:
d(A,B) = sqrt((x2−x1)^2 + (y2−y1)^2)

В файле A хранятся данные о звёздах двух кластеров, 
где H=6, W=4.5 для каждого кластера. 
В каждой строке записана информация 
о расположении на карте одной звезды: 
сначала координата x, затем координата y. 
Значения даны в условных единицах. 
Известно, что количество звёзд не превышает 1000.

В файле Б хранятся данные о звёздах трёх кластеров, 
где H=6, W=5 для каждого кластера. 
Известно, что количество звёзд не превышает 1000. 
Структура хранения информации о звездах в файле Б аналогична файлу А.

Известно, что в файле Б имеются координаты ровно трёх «лишних» точек,
являющихся аномалиями, возникшими в результате помех при передаче данных. 
Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, 
затем найдите два числа: 
  Px — сумму абсцисс центров кластеров, 
  Py — сумму ординат центров кластеров. 

Для файла Б найдите два числа: 
  Q1 — минимальное расстояние между точками, 
       принадлежащими двум различным кластерам, 
  Q2 — максимальное расстояние между точками, 
       принадлежащими двум различным кластерам.

В ответе запишите четыре числа: 
в первой строке — сначала абсолютную 
величину целой части произведения Px×10000, 
затем абсолютную величину целой части произведения Py×10000; 
во второй строке — сначала целую часть произведения Q1×10000, 
затем целую часть произведения Q2×10000.

"""
from math import dist # функция для эвклидова расстояния из библиотеки math


# вспомогательная функция k-средних с медоидами 

def medoid(cluster):
    best, best_sum = None, 10**18 # best_sum - максимальное возможное значение суммы расстояний
    for p in cluster: # p - текущая точка
        s = sum(dist(p, q) for q in cluster)  # сумма расстояний от текущей точки до всех остальных точек кластера
        if s < best_sum: # если сумма расстояний меньше, чем best_sum
            best_sum = s # обновляем best_sum
            best = p # обновляем best
    return best


def clusters(data, centers): 
#каждой точке - индекс ближайшего центра
    labels = []
    for p in data:
        distances = [dist(p, c) for c in centers] # расстояния от текущей точки до всех центров
        labels.append(distances.index(min(distances))) # индекс ближайшего центра
    return labels # возвращаем список индексов ближайших центров для каждой точки


def upd_centers(data, labels, k):
    #новые центры - медоида каждого кластера
    new_centers = [] # новые центры
    for i in range(k): # индекс кластера 
        cluster = [p for p, l in zip(data, labels) if l == i] # список точек, принадлежащих i-му кластеру
        new_centers.append(medoid(cluster)) # медоид кластера
    return new_centers # возвращаем список медоидов кластеров


def k_means(data, k, start_centers):
    #k-средних с медоидами.
    #start_centers - начальные точки, выбранные вручную по диаграмме.
    #сходится, когда центры перестают меняться
    centers = start_centers
    while True:
        labels = clusters(data, centers)
        new_centers = upd_centers(data, labels, k)
        if new_centers == centers:
            break
        centers = new_centers
    return labels, centers


"""
файл А: 2 кластера 
"""

with open('2701_A.txt') as f:
    data_A = [list(map(float, s.replace(',', '.').split())) for s in f]

k = 2

# начальные точки выбираем вручную по точечной диаграмме из LibreOffice
# (по одной точке из каждого видимого кластера)
start = [[5.5, 19], [4.5, 6]]  # верхний кластер (y примерно 17-22) и нижний (y примерно 4.5-9)

labels_A, centers_A = k_means(data_A, k, start)
print('центры A:', centers_A)  # проверка

# Px = сумма абсцисс х, Py = сумма ординат у
px = sum(x for x, y in centers_A) # сумма абсцисс х
py = sum(y for x, y in centers_A) # сумма ординат у
print(abs(int(px * 10000)), abs(int(py * 10000))) # вывод результата

"""
файл Б: 3 кластера + 3 выброса (не учитываем)
"""

with open('2701_B.txt') as f:
    data_B = [list(map(float, s.replace(',', '.').split())) for s in f]

k = 3

# начальные точки по диаграмме: левый (15,12), верхний (17,18), правый (26,7)
start_B = [[15, 12], [17, 18], [26, 7]]

# сначала грубая кластеризация, чтобы найти 3 точки-аномалии (самые далёкие от своего центра)
labels_tmp, centers_tmp = k_means(data_B, k, start_B)
far = sorted([(min(dist(p, c) for c in centers_tmp), p) for p in data_B], reverse=True)
data_B_clean = [p for d, p in far[3:]]  # три верхние точки — выбросы, не участвуют в ответе

labels_B, centers_B = k_means(data_B_clean, k, start_B)
print('центры Б:', centers_B)  # проверка

# списки точек по кластерам (без выбросов)
clusters_B = [[p for p, l in zip(data_B_clean, labels_B) if l == i] for i in range(k)] # проверка

# Q1 минимальное, Q2 максимальное расстояние между точками РАЗНЫХ кластеров
q1, q2 = 10**18, 0
for i in range(k):
    for j in range(i + 1, k):
        for p1 in clusters_B[i]:
            for p2 in clusters_B[j]:
                d = dist(p1, p2)
                if d < q1:
                    q1 = d
                if d > q2:
                    q2 = d

print(int(q1 * 10000), int(q2 * 10000))