ICPC 2019 Asia Regional – Seoul Problem K- Washer > 문제은행 : 정보올림피아드&알고리즘

공지   새로운 정올 베타버전이 공개되었습니다.    자세히보기


4394 : Washer

제한시간
1000 ms   
메모리제한
512 MB   
해결횟수
2 회   
시도횟수
24 회   

문제

You have n clothes and a washer. The washer is large enough to wash all clothes at once. However, we should worry about the color transfer: if we put clothes of different colors in the washer, the dye from one may stain another. Precisely, let ri, gi, bi denote the amount of red, green, blue color of the i-th clothes. When n clothes are washed together, the color transfer c is defined by

 

 

 

 

where r, g, and b are the averages of ri, gi, bi, respectively. The i-th clothes with ri, gi, and bi is defined as a point (ri, gi, bi) in 3-dimensional RGB space. You can assume that no three points (clothes) are on a same line and no four points (clothes) are on a same plane in RGB space.

 

The washer consumes a lot of electricity, and you have to partition n clothes into at most k groups, and run the washer for each group. The total color transfer is the sum of color transfers from each run. Given the color information of n clothes and k, write a program to calculate the minimum total color transfer.​ 


입력형식

Your program is to read from standard input. The first line contains two integers n (1 ≤ n ≤ 100) and k (1 ≤ k ≤ 2). In the following n lines, the i-th line contains three integers ri, gi, bi (0 ≤ ri, gi, bi ≤ 1,000).

 


출력형식

Your program is to write to standard output. Print exactly one line containing the minimum total color transfer, rounded to the sixth decimal point. 


입력 예

복사하기

2 1
36 16 85
74 87 38

출력 예

복사하기

4347.000000

입력 예

복사하기

1 2
12 26 90

출력 예

복사하기

0.000000

입력 예

복사하기

3 2
93 50 26
40 0 77
99 10 29

출력 예

복사하기

822.500000


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP