불개이치의 고민

소스파일: fracs.cpp / fracs.c

추가/수정 사항
좌표 범위는 0에서 10,000 이하 입니다.
3시 33분

좌표 범위에 0도 포함 됩니다.
3시 41분

문제 설명

 지구촌 어딘가에는 아직도 문명의 혜택을 받지 못 하고 살아가는 사람들이 있다. 심지어 전기도 없다. computer 판매상인 불개이치씨는 이런 사람들을 이용해서 돈을 벌 궁리를 하고 있다.

 그의 계획은 개발도상국 사람들에게 초고속인터넷과, 전기를 공급하는 자선사업을 벌이는 것이다. 여타 기업의 지원을 받아서 집집마다 초고속인터넷과 전기를 공급해준다. 물론 자신의 돈도 쪼금 들어가겠지만 , 그것은 훗날을 위한 투자비용이다. 초고속 인터넷과 전기가 공급이 된다 치자. 그런데 뭔가 허전하다. 바로 컴퓨터가 없다. 이점이 불개이치씨가 노리고 있는 점이다. 초고속 인터넷과 전기만 공급해주면 알아서 컴퓨터를 사게 된다는 논리이다.

불개이치씨가 이런 계획을 진행하는데 가장 큰 걸림돌이 되는 것은 투자 자금이다. 즉 최소의 비용으로 집집마다 초고속 인터넷과 전기를 공급해주어야 하는 것이다. 불개이치씨를 도와서 초고속 인터넷과 전기를 최소 비용으로 공급해보자.

 당신이 해야 할일은 한 마을에 초고속 인터넷과 전기를 공급하는 것이다. 마을은 평평하다고 가정한다. 마을은 2차원 plane 이고 , 각각의 집은 점으로 표현된다. 단, 두 집의 좌표가 같은 경우는 없다고 하자. 한 마을에는 n개의 집이 존재한다. 초고속 인터넷선과 , 전기선은 plane에서 line(선) 으로 표현된다. 초고속 인터넷 선과, 전기선은 각각 두 가지 종류가 있다. main line이 있고 local line이 있다. main line은 휘어지지 않고 일직선으로 지나간다. 초고속 인터넷 선은 y 좌표축에 평행하게 지나가고, 전기선은 x좌표축에 평행하게 지나간다. 그리고 각각의 집은 이 초고속 인터넷의 main line 에 연결해서 초고속인터넷을 공급받고, 전기의 main line 에 연결해서 전기를 공급받는다. 이 때 각각의 집과 main line의 연결이 local line 이다. 

 main line은 건설 회사의 지원을 받기로 해서 최대 m개까지 공짜로 전기선 main line과 초고속 인터넷 main line 건설이 가능하다. 즉, 각각의 main line을 m개씩 건설이 가능하다. 돈이 드는 것은 local line이다. 이것은 불개이치씨의 사비로 해결해야 한다.

 초고속인터넷선의 local line 을 연결하는데 드는 비용은 아래와 같다. 현재 연결하려는 집의 좌표가 x0, y0 이고, 초고속인터넷선의 main line의 x1,y1 지점과 연결하려고 한다면, 비용은 |x0-x1| + |y0-y1| 이 된다.

 전기선의 local line 을 연결하는데 드는 비용은 아래와 같다. 현재 연결하려는 집의 좌표가 x0, y0 이고, 전기선의 main line의 x1,y1 지점과 연결하려 한다면, 비용은 (x0 - x1)^2 + (y0 - y1)^2 이 된다.

 최대 m개의 main line을(두 종류 각각) 건설할 수 있고, main line의 위치는 마음대로 결정 할 수 있으며, local line의 연결도 마음대로 할 수 있다. local line이 어떤 전기 main line이나 초고속 인터넷 main line과 연결되더라도 상관없다. 다만 모든 집은 초고속 인터넷과 전기를 사용할 수 있도록 연결 되어야 한다. 이 때 최소 비용을 구하시오.

입력 (INPUT.TXT)

 첫줄에 마을에 있는 집의 수인 정수 n이 주어진다. 둘째 줄에는 최대 건설할 수 있는 전기선과 도시가스선의 개수인 m이 주어진다. 이후 n개의 줄에는 각각 집의 좌표가 주어진다. x좌표와 y좌표를 나타내는 두개의 수가 주어진다. 각각의 좌표는 정수가 아니고 소수점 둘째자리까지 정확도를 갖는 실수다.

출력 (OUTPUT.TXT)

 첫줄에 최소비용만 출력한다. 소수점 둘째자리에서 반올림해서 소수점 첫째자리 까지 출력한다.

<예제 설명>

main line 은 그림과 같이 배치하고, local line은 main line 과 직교하게 연결하면 최적해가 된다. 1번 집에 인터넷 공급에 8, 전기 공급에 1의 비용이 들고, 2번 집은 인터넷 공급에 5, 전기 공급에 4의 비용이 들고, 3번 집은 인터넷 공급에 0, 전기 공급에 4비용이 들고 , 4번 집은 인터넷 공급에 3, 전기 공급에 0의 비용이 든다. 마지막 5번 집은 인터넷 공급에 4, 전기 공급에 1 비용이 소비된다. 다 더하면 30이 된다.

제한시간: 1.0초 / 메모리제한: 16MB

데이터의 50% , n<=100 , m<=50 이다.

나머지 50% 는 , n<=1000, m<=50 이다.