시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 160 MB | 376 | 128 | 94 | 33.813% |
창영이는 생일 선물로 크레용 N개를 받았다. 각 크레용의 색은 빨강, 초록, 파랑이 혼합으로 나타낼 수 있다. i번 크레용의 색은 빨강 성분 Ri, 초록 성분 Gi, 파랑 성분 Bi로 나타낼 수 있다.
i번 크레용과 j번 크레용의 거리는 max(|Ri - Rj|, |Gi - Gj|, |Bi - Bj|) 이다. 크레용 여러 개의 채도는 두 크레용의 거리 중 가장 큰 값이다.
창영이는 가지고 있는 크레용 중에서 채도가 가장 작게 되는 크레용 K개를 고르려고 한다. 이때, 어떻게 고르면 채도가 최소가 되는지 구하는 프로그램을 작성하시오.
첫째 줄에 N과 K가 주어진다. (2 ≤ K ≤ N ≤ 100,000)
다음 N개 줄에는 각 크레용의 색상 성분 Ri, Gi, Bi가 주어진다. (0 ≤ Ri, Gi, Bi ≤ 255)
첫째 줄에 K개를 골랐을 때, 가장 작은 채도를 출력한다. 다음 K개 줄에는 고른 크레용의 R, G, B 성분을 한 줄에 하나씩 출력한다.
2 2 1 3 2 2 6 4
3 1 3 2 2 6 4
3 2 3 3 4 1 6 4 1 1 2
2 3 3 4 1 1 2
5 3 6 6 4 6 2 7 3 1 3 4 1 5 6 2 6
2 6 2 7 4 1 5 6 2 6