#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# UPMC - c.durr - 2015-2016
# Conception et Pratique de l'Algorithmique
# TME 9 - algorithme de flux pour k-center

from math import hypot
from sys import argv


def streamPoints(filename):
    "lit un fichier de coordonnées x,y séparées par un blanc "
    with open(filename) as fp:
        for line in fp:
            tab = line.strip().split(' ')
            x = float(tab[0])
            y = float(tab[1])
            yield (x, y) + tuple(tab[2:])   # garder evt. le nom de ville


def dist(a, b):
    '''distance euclidienne
    '''
    return hypot(a[0]-b[0], a[1]-b[1])


def distSet(a, S):
    '''distance entre un point a et un ensemble S
    '''
    return min((dist(a, b) for b in S), default=float('inf'))


class KCenter:

    def __init__(self, k):
        self.k = k
        assert k >= 1
        self.R = []
        self.tau = -1
        self.distmin = float('inf')    # pour phase d'initialisation
        self.argmin = None

    def update(self, item):
        if self.tau == -1:             # phase d'initialisation
            d = distSet(item, self.R)
            if d < self.distmin:
                self.distmin = d       # maintenir point le plus proche
                self.argmin = len(self.R)
            self.R.append(item)
            if len(self.R) == self.k + 1:
                i = self.argmin
                self.R = self.R[:i] + self.R[i+1:]
                self.tau = self.distmin
        else:                          # phase de croisière
            if distSet(item, self.R) > 2 * self.tau:
                self.R.append(item)
                while len(self.R) > self.k:
                    self.tau *= 2      # doubling
                    R1 = []            # cherche ensemble maximal R'
                    for a in self.R:
                        if distSet(a, R1) >= self.tau:
                            R1.append(a)
                    self.R = R1

    def value(self):
        return self.R


if __name__ == "__main__":
    if len(argv) != 3:
        print("usage: kcenter.py <k> <gpsfilename>")
        exit(0)

    k = int(argv[1])
    c = KCenter(k)

    for p in streamPoints(argv[2]):
        c.update(p)

    sol = c.value()
    for p in sol:
        print(" ".join(map(str, p)))