题解 | #K-Means聚类下的Anchor优化输出#

def distance(box1, box2):
    w1, h1 = box1
    w2, h2 = box2
    S1 = min(w1, w2) * min(h1, h2)
    S2 = w1 * h1 + w2 * h2 - S1

    d = 1 - S1 / S2

    return d

class KMeans:
    def __init__(self, N, K, boxes):
        self.N = N
        self.K = K
        self.boxes = boxes

        self.group = [0 for _ in range(N)]
        self.count = [0 for _ in range(K)]

        self.centers = list(boxes[:K])
        return

    def k_means(self, T, max_error=1.0e-4):
        step = 0
        error = 1.0

        while step < T and error > max_error:
            self.create_group()
            centers_cur = self.cal_center()
            error = self.cal_error(centers_cur)
            self.centers = centers_cur
            step += 1
        return

    def cal_error(self, centers_cur):
        error = 0.0
        for ii in range(self.K):
            error += distance(self.centers[ii], centers_cur[ii])
        return error

    def create_group(self):
        count = [0 for _ in range(self.K)]
        for ii in range(self.N):
            d = float('inf')
            for jj in range(self.K):
                d1 = distance(self.boxes[ii], self.centers[jj])
                if d1 < d:
                    d = d1
                    self.group[ii] = jj
            count[self.group[ii]] += 1
        self.count = count
        return

    def cal_center(self):
        centers = self.centers
        for ii in range(self.K):
            if self.count[ii] > 0:
                w = 0
                h = 0
                for jj in range(self.N):
                    if self.group[jj] == ii:
                        w += self.boxes[jj][0]
                        h += self.boxes[jj][1]
                w = w / self.count[ii]
                h = h / self.count[ii]
                centers[ii] = (int(w), int(h))
        return centers

    def print_centers(self):
        Swh = []
        for ii in range(self.K):
            w = self.centers[ii][0]
            h = self.centers[ii][1]
            S = w * h
            Swh.append((S, w, h))
        Swh.sort(reverse=True)
        for ii in range(self.K):
            print(Swh[ii][1], Swh[ii][2])


def read_in():
    N, K, T = map(int, input().split())
    boxes = []
    for _ in range(N):
        boxes.append(tuple(map(int, input().split())))

    boxes = tuple(boxes)
    return N, K, T, boxes

if __name__ == '__main__':
    readin = read_in()
    km = KMeans(readin[0], readin[1], readin[3])
    km.k_means(readin[2])
    km.print_centers()