시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 26 12 9 39.130%

문제

재현이는 BOJ에서 가장 아름다운 정원을 소유하고 있는 사람으로, 정원에 n개의 꽃을 심어놓았다. 모든 꽃들이 화사하게 핀 여름날. 재현이는 아름다운 꽃들을 보고 있으니 갑자기 대한민국의 경제가 걱정되기 시작해서, 두명의 정원사 박승원과 신승원을 고용해서 실업률을 낮추고 경제를 활성화시키려고 한다.

정원은 가로가 l미터, 세로가 w미터인 직사각형 모양이며, 가로 세로가 1미터인 l*w 개의 정사각형 칸으로 분할되어 있다. 정원은 x축과 y축에 평행하며, 정원 내부에 있는 모든 정사각형 칸은 1 ≤ x ≤ l, 1 ≤ y ≤ w인 정수 좌표 (x,y) 로 표현할 수 있다.

만약 재현이가 (l1,w1), (l1,w2), (l2,w1), (l2,w2)를 모서리로 갖는 직사각형을 골랐다면 이 영역은 1 ≤ l1 ≤ l2 ≤ l, 1 ≤ w1 ≤ w2 ≤ w 를 만족하는 모든 칸 (x,y)를 포함하며 이 영역의 둘레는 2 · (l2 − l1 + 1) + 2 · (w2 − w1 + 1) 이다.

재현이가 하고 싶은 일은 이 정원에 두개의 겹치지 않는 직사각형 모양의 울타리를 치고, 그 직사각형 영역 안에 들어있는 장미의 개수를 모두 동일하게 k개로 유지하는 것이다.

재현이는 이렇게 생긴 두개의 구역을 각각 박승원과 신승원에게 할당할 계획이다. 하지만, 애석하게도 울타리는 수입 제품이기 때문에 경제를 살리는데 아무런 도움이 안된다. 때문에 재현이는 울타리를 치는 영역의 둘레를 최소화해서 내수 시장을 활성화시킬 계획이다.

정원의 크기와 장미들의 위치, 그리고 정원사에게 할당하고 싶은 장미의 수를 입력받아, 최소한의 길이로 울타리를 치면서 장미도 지정해 준 대로 들어있는 두 영역을 구하는 프로그램을 작성하시오.

두 영역은 서로 겹치면 안되며, 영역 내부에 정확히 k그루의 장미가 있어야 한다. 또한, 두 울타리가 겹치는 부분에는 울타리를 두번 설치해준다.

입력

첫번째 줄에는 정원의 길이와 폭인 l,w가 주어진다. (1 ≤ l,w ≤ 250)

두번째 줄에는 전체 장미의 수 n, 두 승원이가 할당받을 장미의 수 k가 주어진다. (2 ≤ n ≤ 5000 , 1 ≤ k ≤ n/2)

이후 i개의 줄에 i번째 장미가 있는 칸을 의미하는 두 정수 li, wi (1 ≤ li ≤ l, 1 ≤ wi ≤ w) 가 주어진다.

출력

둘레의 합이 최소인 두 영역을 구한 뒤, 두 영역의 둘레 길이의 합을 구한다. 만약 그러한 영역을 구할 수 없었다면 NO를 출력한다.

예제 입력

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

예제 출력

22

힌트

출처

Olympiad > International Olympiad in Informatics > IOI 2005 1번

  • 문제를 번역한 사람: koosaga