균등 구간 클러스터링
면접 대비시간 제한5초메모리 제한128 MB
점들을 좌표 기준으로 정렬한 뒤 거의 동일한 크기의 K개 연속 그룹으로 나누고 각 그룹의 좌표 평균을 출력합니다.
문제
평면 위에 있는 양 N마리의 좌표가 주어진다. 양들을 (x, y) 좌표의 사전순, 즉 x가 작은 순서로 정렬하고 x가 같으면 y가 작은 순서로 정렬한다.
정렬된 순서를 유지한 채 양들을 K개의 비어 있지 않은 연속 구간으로 나눈다. 구간의 크기는 가능한 한 같아야 한다. q = floor(N / K), r = N mod K라고 하면, 앞의 r개 구간은 각각 q + 1개의 점을 가지고 나머지 구간은 각각 q개의 점을 가진다.
각 구간을 하나의 클러스터로 보고, 그 클러스터에 속한 점들의 산술평균 좌표를 클러스터 중심으로 출력하라. 중심은 구간이 만들어지는 순서대로 출력한다.
입력
첫째 줄에 양의 수 N과 클러스터의 수 K가 공백으로 구분되어 주어진다.
다음 N개의 줄에는 각 양의 좌표 Xi Yi가 공백으로 구분되어 주어진다.
출력
K개의 줄을 출력한다. i번째 줄에는 i번째 클러스터 중심의 x좌표와 y좌표를 공백으로 구분하여 출력한다.
각 좌표는 소수점 아래 정확히 여섯 자리까지 출력한다.
제한
1 <= K < N <= 10001 <= K <= 1000 <= Xi, Yi <= 10000- 입력의 모든 좌표는 정수이다.