시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 160 MB3761289433.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 성분을 한 줄에 하나씩 출력한다. 

예제 입력 1

2 2
1 3 2
2 6 4

예제 출력 1

3
1 3 2
2 6 4

예제 입력 2

3 2
3 3 4
1 6 4
1 1 2

예제 출력 2

2
3 3 4
1 1 2

예제 입력 3

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

예제 출력 3

2
6 2 7
4 1 5
6 2 6
W3sicHJvYmxlbV9pZCI6IjI4MDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwNmNcdWI4MDhcdWM2YTkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWMwZGRcdWM3N2MgXHVjMTIwXHViYjNjXHViODVjIFx1ZDA2Y1x1YjgwOFx1YzZhOSBOXHVhYzFjXHViOTdjIFx1YmMxYlx1YzU1OFx1YjJlNC4gXHVhYzAxIFx1ZDA2Y1x1YjgwOFx1YzZhOVx1Yzc1OCBcdWMwYzlcdWM3NDAgXHViZTY4XHVhYzE1LCBcdWNkMDhcdWI4NWQsIFx1ZDMwY1x1Yjc5MVx1Yzc3NCBcdWQ2M2NcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIGlcdWJjODggXHVkMDZjXHViODA4XHVjNmE5XHVjNzU4IFx1YzBjOVx1Yzc0MCBcdWJlNjhcdWFjMTUgXHVjMTMxXHViZDg0IFI8c3ViPmk8XC9zdWI+LCBcdWNkMDhcdWI4NWQgXHVjMTMxXHViZDg0IEc8c3ViPmk8XC9zdWI+LCBcdWQzMGNcdWI3OTEgXHVjMTMxXHViZDg0IEI8c3ViPmk8XC9zdWI+XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5pXHViYzg4IFx1ZDA2Y1x1YjgwOFx1YzZhOVx1YWNmYyBqXHViYzg4IFx1ZDA2Y1x1YjgwOFx1YzZhOVx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgbWF4KHxSPHN1Yj5pPFwvc3ViPiAtIFJqfCwgfEc8c3ViPmk8XC9zdWI+IC0gRzxzdWI+ajxcL3N1Yj58LCB8QjxzdWI+aTxcL3N1Yj4gLSBCPHN1Yj5qPFwvc3ViPnwpIFx1Yzc3NFx1YjJlNC4gXHVkMDZjXHViODA4XHVjNmE5IFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVjYzQ0XHViM2M0XHViMjk0IFx1YjQ1MCBcdWQwNmNcdWI4MDhcdWM2YTlcdWM3NTggXHVhYzcwXHViOWFjIFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YWMxMlx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjYzNkXHVjNjAxXHVjNzc0XHViMjk0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVkMDZjXHViODA4XHVjNmE5IFx1YzkxMVx1YzVkMFx1YzExYyBcdWNjNDRcdWIzYzRcdWFjMDAgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1YWM4YyBcdWI0MThcdWIyOTQgXHVkMDZjXHViODA4XHVjNmE5IEtcdWFjMWNcdWI5N2MgXHVhY2UwXHViOTc0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVhY2UwXHViOTc0XHViYTc0IFx1Y2M0NFx1YjNjNFx1YWMwMCBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IEsgJmxlOyBOICZsZTsgMTAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWQwNmNcdWI4MDhcdWM2YTlcdWM3NTggXHVjMGM5XHVjMGMxIFx1YzEzMVx1YmQ4NCBSPHN1Yj5pPFwvc3ViPiwgRzxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyBSPHN1Yj5pPFwvc3ViPiwgRzxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+ICZsZTsgMjU1KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgS1x1YWMxY1x1Yjk3YyBcdWFjZThcdWI3OTBcdWM3NDQgXHViNTRjLCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1Y2M0NFx1YjNjNFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjJlNFx1Yzc0YyBLXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjZTBcdWI5NzggXHVkMDZjXHViODA4XHVjNmE5XHVjNzU4IFIsIEcsIEIgXHVjMTMxXHViZDg0XHVjNzQ0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyODAyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUEFTVEVMRSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gcmVjZW50bHkgZ290IE4gY3JheW9ucyBhcyBhIGdpZnQuIFRoZSBjb2xvciBvZiBlYWNoIGNyYXlvbiBpcyBhIGNvbWJpbmF0aW9uIG9mIHRocmVlIHByaW1hcnkgY29sb3JzOiByZWQsIGdyZWVuIGFuZCBibHVlLiBUaGUgY29sb3Igb2YgdGhlIGk8c3VwPnRoPFwvc3VwPiBjcmF5b24gaXMgcmVwcmVzZW50ZWQgd2l0aCB0aHJlZSBpbnRlZ2VyczogUjxzdWI+aTxcL3N1Yj4gZm9yIHRoZSByZWQsIEc8c3ViPmk8XC9zdWI+IGZvciB0aGUgZ3JlZW4gYW5kIEI8c3ViPmk8XC9zdWI+IGZvciB0aGUgYmx1ZSBjb21wb25lbnQuPFwvcD5cclxuXHJcbjxwPlRoZSBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIGk8c3VwPnRoPFwvc3VwPiBhbmQgdGhlIGo8c3VwPnRoPFwvc3VwPiBjcmF5b24gaXMgbWF4KHxSPHN1Yj5pPFwvc3ViPiZuYnNwOy0gUmp8LCB8RzxzdWI+aTxcL3N1Yj4mbmJzcDstIEc8c3ViPmo8XC9zdWI+fCwgfEI8c3ViPmk8XC9zdWI+Jm5ic3A7LSBCPHN1Yj5qPFwvc3ViPnwpLiBUaGUgY29sb3JmdWxuZXNzIG9mIGEgc3Vic2VxdWVuY2Ugb2YgY3JheW9ucyBpcyBlcXVhbCB0byB0aGUgbGFyZ2VzdCBkaWZmZXJlbmNlIGJldHdlZW4gYW55IHR3byBjcmF5b25zIGluIHRoZSBzdWJzZXF1ZW5jZS48XC9wPlxyXG5cclxuPHA+TWlya28gbmVlZHMgYSBzdWJzZXF1ZW5jZSB3aXRoIEsgY3JheW9ucyB3aXRoIHRoZSBzbWFsbGVzdCBjb2xvcmZ1bG5lc3MgZm9yIGhpcyBkcmF3aW5nLiBUaGUgc3Vic2VxdWVuY2UgZG9lcyBub3QgaGF2ZSB0byBiZSBjb25zZWN1dGl2ZS4gRmluZCBpdCE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGludGVnZXJzIE4gYW5kIEsgKDIgJmxlOyBLICZsZTsgTiAmbGU7IDEwMCAwMDApLjxcL3A+XHJcblxyXG48cD5UaGUgaTxzdXA+dGg8XC9zdXA+IG9mIHRoZSBmb2xvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHRocmVlIGludGVnZXJzIFI8c3ViPmk8XC9zdWI+LCBHPHN1Yj5pPFwvc3ViPiBhbmQgQjxzdWI+aTxcL3N1Yj4gKDAgJmxlOyBSPHN1Yj5pPFwvc3ViPiwgRzxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+ICZsZTsgMjU1KS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIHNtYWxsZXN0IGNvbG9yZnVsbmVzcyBvZiBhIHN1YnNlcXVlbmNlIHdpdGggSyBjcmF5b25zLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIEsgbGluZXMgc2hvdWxkIGNvbnRhaW4gdGhlIFIsIEcgYW5kIEIgdmFsdWVzIG9mIHRoZSBjb2xvcnMgb2YgdGhlIGNyYXlvbnMgaW4gdGhlIHN1YnNlcXVlbmNlLCBpbiBhbnkgb3JkZXIuIEFueSBzdWJzZXF1ZW5jZSB0aGF0IHlpZWxkcyB0aGUgc21hbGxlc3QgY29sb3JmdWxuZXNzIHdpbGwgYmUgYWNjZXB0ZWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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

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