기지국 > 문제은행

본문 바로가기


알고리즘 다이나믹2

2038 : 기지국

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 90 회    시도횟수: 316 회   



KOI 무선통신사는 직선의 통신라인 상에 기지국들을 설치하여 주변의 주요 건물들을 모두 통신범위에 포함 시키고자 한다. 각 기지국의 통신범위는 기지국을 중심으로 하고 밑변이 통신라인과 평행한 정사각형이고, 이 정사각형의 한 변의 길이를 통신폭이라 한다. 기지국들의 총 설치비용은 각 기지국의 통신폭의 합이고, 기지국의 수와는 무관하다.

 

평면상에 주요건물들의 위치가 주어졌을 때, 기지국들을 설치하여 모든 주요건물을 통신범위에 포함하는 최소의 총 설치비용을 구하는 프로그램을 작성하시오. 통신라인은 -축과 일치하고 건물들의 위치좌표는 정수이다. 통신라인 상에는 건물이 위치하지 않으며, 모든 건물들의 위치는 서로 다르다.

 

다음 그림의 예를 보면,

  1. 첫 번째 기지국의 위치는 (-2, 0) 이고, 통신폭이 4인 정사각형의 통신범위로 세 개의 건물을 포함한다.
  2. 두 번째 기지국의 위치는 (2, 0)이고, 통신폭이 2인 정사각형의 통신범위로 두 개의 건물을 포함한다.
  3. 세 번째 기지국의 위치는 (6.5, 0) 이고, 통신폭이 3인 정사각형의 통신범위로 두 개의 건물을 포함한다.

부분 점수는 없다.

 

75aaf69980fa1f33c5b54a688ed39a00_1450936 


첫째 줄에는 건물의 개수 N이 주어지고(1≤N≤10,000), 그 다음 N개의 줄에는 한 줄에 한 건물의 x-좌표와 y-좌표가 빈 칸을 사이에 두고 차례로 주어진다. x-좌표와 y-좌표는 절대값이 1,000,000 이하인 정수이다.


최소의 총 설치비용(기지국의 통신범위를 나타내는 통신폭의 총합)을 첫째 줄에 출력한다.

[Copy]
7 
-2 -1 
-4 -1 
0 2 
3 1 
5 1 
1 -1 
8 -1
[Copy]
9





HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.