시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 160 MB 156 53 40 35.398%

문제

창영이는 생일 선물로 크레용 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 성분을 한 줄에 하나씩 출력한다. 

예제 입력 1

5 3
6 6 4
6 2 7
3 1 3
4 1 5
6 2 6

예제 출력 1

2
6 2 7
4 1 5
6 2 6
W3sicHJvYmxlbV9pZCI6IjI4MDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwNmNcdWI4MDhcdWM2YTkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWMwZGRcdWM3N2MgXHVjMTIwXHViYjNjXHViODVjIFx1ZDA2Y1x1YjgwOFx1YzZhOSBOXHVhYzFjXHViOTdjIFx1YmMxYlx1YzU1OFx1YjJlNC4gXHVhYzAxIFx1ZDA2Y1x1YjgwOFx1YzZhOVx1Yzc1OCBcdWMwYzlcdWM3NDAgXHViZTY4XHVhYzE1LCBcdWNkMDhcdWI4NWQsIFx1ZDMwY1x1Yjc5MVx1Yzc3NCBcdWQ2M2NcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIGlcdWJjODggXHVkMDZjXHViODA4XHVjNmE5XHVjNzU4IFx1YzBjOVx1Yzc0MCBcdWJlNjhcdWFjMTUgXHVjMTMxXHViZDg0IFI8c3ViPmk8XC9zdWI+LCBcdWNkMDhcdWI4NWQgXHVjMTMxXHViZDg0IEc8c3ViPmk8XC9zdWI+LCBcdWQzMGNcdWI3OTEgXHVjMTMxXHViZDg0IEI8c3ViPmk8XC9zdWI+XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5pXHViYzg4IFx1ZDA2Y1x1YjgwOFx1YzZhOVx1YWNmYyBqXHViYzg4IFx1ZDA2Y1x1YjgwOFx1YzZhOVx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgbWF4KHxSPHN1Yj5pPFwvc3ViPiAtIFJqfCwgfEc8c3ViPmk8XC9zdWI+IC0gRzxzdWI+ajxcL3N1Yj58LCB8QjxzdWI+aTxcL3N1Yj4gLSBCPHN1Yj5qPFwvc3ViPnwpIFx1Yzc3NFx1YjJlNC4gXHVkMDZjXHViODA4XHVjNmE5IFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVjYzQ0XHViM2M0XHViMjk0IFx1YjQ1MCBcdWQwNmNcdWI4MDhcdWM2YTlcdWM3NTggXHVhYzcwXHViOWFjIFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YWMxMlx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjYzNkXHVjNjAxXHVjNzc0XHViMjk0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVkMDZjXHViODA4XHVjNmE5IFx1YzkxMVx1YzVkMFx1YzExYyBcdWNjNDRcdWIzYzRcdWFjMDAgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1YWM4YyBcdWI0MThcdWIyOTQgXHVkMDZjXHViODA4XHVjNmE5IEtcdWFjMWNcdWI5N2MgXHVhY2UwXHViOTc0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVjNWI0XHViNWJiXHVhYzhjIFx1YWNlMFx1Yjk3NFx1YmE3NCBcdWNjNDRcdWIzYzRcdWFjMDAgXHVjZDVjXHVjMThjXHVhYzAwIFx1YjQxOFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBLICZsZTsgTiAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVkMDZjXHViODA4XHVjNmE5XHVjNzU4IFx1YzBjOVx1YzBjMSBcdWMxMzFcdWJkODQgUjxzdWI+aTxcL3N1Yj4sIEc8c3ViPmk8XC9zdWI+LCBCPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgUjxzdWI+aTxcL3N1Yj4sIEc8c3ViPmk8XC9zdWI+LCBCPHN1Yj5pPFwvc3ViPiAmbGU7IDI1NSk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIEtcdWFjMWNcdWI5N2MgXHVhY2U4XHViNzkwXHVjNzQ0IFx1YjU0YywgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWNjNDRcdWIzYzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWIyZTRcdWM3NGMgS1x1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhY2UwXHViOTc4IFx1ZDA2Y1x1YjgwOFx1YzZhOVx1Yzc1OCBSLCBHLCBCIFx1YzEzMVx1YmQ4NFx1Yzc0NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjgwMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBBU1RFTEUiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIHJlY2VudGx5IGdvdCBOIGNyYXlvbnMgYXMgYSBnaWZ0LiBUaGUgY29sb3Igb2YgZWFjaCBjcmF5b24gaXMgYSBjb21iaW5hdGlvbiBvZiB0aHJlZSBwcmltYXJ5IGNvbG9yczogcmVkLCBncmVlbiBhbmQgYmx1ZS4gVGhlIGNvbG9yIG9mIHRoZSBpPHN1cD50aDxcL3N1cD4gY3JheW9uIGlzIHJlcHJlc2VudGVkIHdpdGggdGhyZWUgaW50ZWdlcnM6IFI8c3ViPmk8XC9zdWI+IGZvciB0aGUgcmVkLCBHPHN1Yj5pPFwvc3ViPiBmb3IgdGhlIGdyZWVuIGFuZCBCPHN1Yj5pPFwvc3ViPiBmb3IgdGhlIGJsdWUgY29tcG9uZW50LjxcL3A+XHJcblxyXG48cD5UaGUgZGlmZmVyZW5jZSBiZXR3ZWVuIHRoZSBpPHN1cD50aDxcL3N1cD4gYW5kIHRoZSBqPHN1cD50aDxcL3N1cD4gY3JheW9uIGlzIG1heCh8UjxzdWI+aTxcL3N1Yj4mbmJzcDstIFJqfCwgfEc8c3ViPmk8XC9zdWI+Jm5ic3A7LSBHPHN1Yj5qPFwvc3ViPnwsIHxCPHN1Yj5pPFwvc3ViPiZuYnNwOy0gQjxzdWI+ajxcL3N1Yj58KS4gVGhlIGNvbG9yZnVsbmVzcyBvZiBhIHN1YnNlcXVlbmNlIG9mIGNyYXlvbnMgaXMgZXF1YWwgdG8gdGhlIGxhcmdlc3QgZGlmZmVyZW5jZSBiZXR3ZWVuIGFueSB0d28gY3JheW9ucyBpbiB0aGUgc3Vic2VxdWVuY2UuPFwvcD5cclxuXHJcbjxwPk1pcmtvIG5lZWRzIGEgc3Vic2VxdWVuY2Ugd2l0aCBLIGNyYXlvbnMgd2l0aCB0aGUgc21hbGxlc3QgY29sb3JmdWxuZXNzIGZvciBoaXMgZHJhd2luZy4gVGhlIHN1YnNlcXVlbmNlIGRvZXMgbm90IGhhdmUgdG8gYmUgY29uc2VjdXRpdmUuIEZpbmQgaXQhPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBpbnRlZ2VycyBOIGFuZCBLICgyICZsZTsgSyAmbGU7IE4gJmxlOyAxMDAgMDAwKS48XC9wPlxyXG5cclxuPHA+VGhlIGk8c3VwPnRoPFwvc3VwPiBvZiB0aGUgZm9sb3dpbmcgTiBsaW5lcyBjb250YWlucyB0aHJlZSBpbnRlZ2VycyBSPHN1Yj5pPFwvc3ViPiwgRzxzdWI+aTxcL3N1Yj4gYW5kIEI8c3ViPmk8XC9zdWI+ICgwICZsZTsgUjxzdWI+aTxcL3N1Yj4sIEc8c3ViPmk8XC9zdWI+LCBCPHN1Yj5pPFwvc3ViPiAmbGU7IDI1NSkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBzbWFsbGVzdCBjb2xvcmZ1bG5lc3Mgb2YgYSBzdWJzZXF1ZW5jZSB3aXRoIEsgY3JheW9ucy48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBLIGxpbmVzIHNob3VsZCBjb250YWluIHRoZSBSLCBHIGFuZCBCIHZhbHVlcyBvZiB0aGUgY29sb3JzIG9mIHRoZSBjcmF5b25zIGluIHRoZSBzdWJzZXF1ZW5jZSwgaW4gYW55IG9yZGVyLiBBbnkgc3Vic2VxdWVuY2UgdGhhdCB5aWVsZHMgdGhlIHNtYWxsZXN0IGNvbG9yZnVsbmVzcyB3aWxsIGJlIGFjY2VwdGVkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #6 5번

  • 문제를 번역한 사람: baekjoon
  • 데이터를 추가한 사람: sgc109