Problem : 244 - Garden

Problem Statistics

Solved Member: 21　　Submission: 86　　User Tried: 23

Statement:

拜特曼先生擁有拜特城中最美麗的花園。拜特曼先生在花園中種了n株玫瑰。夏天來臨了這些玫瑰長的又大又美麗。拜特曼先生知道他無法單獨一人照顧所有的玫瑰，所以他決定雇用兩個園丁來幫忙。拜特曼先生希望劃定兩塊矩形區域，讓兩個園丁一人照顧一塊區域中的玫瑰。這兩塊矩形區域不可重疊，而且任一區域都必須包含恰好k株玫瑰。

拜特曼先生希望在兩塊矩形區域邊界各建一道圍籬，但是因為他很缺錢，所以拜特曼先生希望圍籬越短越好。你的工作是幫拜特曼先生選擇這兩塊矩形區域。

拜特曼先生的花園是一個l公尺長，w公尺寬的矩形。花園包含了l‧w個一公尺乘一公尺(一公尺見方)的正方形區域。我們使用一橫軸及縱軸與花園週邊平行的座標系。所有的一公尺見方的正方形區域均以整數座標 (x, y) 表示，其中1 ≤ x ≤ l，1 ≤ y ≤ w。每一個一公尺見方的正方形區域可包含任意數目的玫瑰。

我們所要選取的兩個矩形區域其週邊必須與花園週邊平行，並且其四個角落均必須為整數座標。一個矩形區域的四個角落方格座標為(l₁, w₁)，(l₁, w₂)，(l₂, w₁)，及(l₂, w₂)，並且1 ≤ l₁ ≤ l₂ ≤ l，1 ≤ w₁ ≤ w₂ ≤ w。

• 任何座標為 (x, y)，l₁ ≤ x ≤ l₂且w₁ ≤ y ≤ w₂ 的一公尺見方正方形區域均位於此矩形區域中。
• 此矩形區域的周邊長度為 2(l₂ - l₁+ 1) + 2(w₂ - w₁+ 1)。

這兩塊矩形區域不可重疊，意即他們不可同時包含同一個一公尺見方正方形區域。同時，即使這兩塊矩形區域的周邊有重疊，他們也是由不同的圍籬所包圍。

Task:

編寫一程式：
• 由標準輸入讀入花園的大小，玫瑰的總株數，玫瑰的座標，以及兩塊矩形區域內應有的玫瑰株數。
• 找出能滿足所有給定條件，且擁有最小週邊長度和的兩個矩形區域。
• 將兩個互不重疊，且各自擁有k株玫瑰矩形區域的最小周邊和輸出至標準輸出。

Input:Output:

輸入的第一行包含兩個整數(由一個空白分開)： l 及w (1 ≤ l, w ≤ 250)，分別代表花園的長與寬。輸入的第二行包含兩個整數(由一個空白分開)：n 及k (2 ≤ n ≤ 5000, 1 ≤ k ≤ n/2)，分別代表玫瑰的總株數以及矩形區域內應有的玫瑰株數。接下來的n行為玫瑰位置的座標。一行代表一株玫瑰。第 i+2 行包含兩個整數(由一個空白分開)： l_i, w_i (1 ≤ l_i ≤ l，1 ≤ w_i ≤ w)，分別代表第i株玫瑰所在正方形的座標。一個一公尺見方的正方形內可能有超過一株玫瑰。

在50%的測試資料中，花園的大小滿足， l, w ≤ 40。

你的程式應只輸出一行，該行只有一個數字，代表兩個互不重疊，且各自擁有k株玫瑰矩形區域的最小周邊和。如果符合條件的矩形不存在，則輸出一字串 NO。

Sample Input:Sample Output:

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

HINT:

Source:

IOI 2005

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	500ms	32768kb
1-1	500ms	32768kb	5
1-2	500ms	32768kb
2-1	500ms	32768kb	5
2-2	500ms	32768kb
3	500ms	32768kb	5
4	500ms	32768kb	5
5-1	500ms	32768kb	5
5-2	500ms	32768kb
6-1	500ms	32768kb	5
6-2	500ms	32768kb
7-1	500ms	32768kb	5
7-2	500ms	32768kb
8-1	500ms	32768kb	5
8-2	500ms	32768kb
9	500ms	32768kb	5
10-1	500ms	32768kb	5
10-2	500ms	32768kb
11	500ms	32768kb	5
12-1	500ms	32768kb	5
12-2	1000ms	32768kb
13-1	500ms	32768kb	5
13-2	500ms	32768kb
14	500ms	32768kb	5
15-1	500ms	32768kb	5
15-2	500ms	32768kb
16-1	500ms	32768kb	5
16-2	500ms	32768kb
17-1	500ms	32768kb	5
17-2	500ms	32768kb
18-1	500ms	32768kb	5
18-2	500ms	32768kb
19-1	500ms	32768kb	5
19-2	500ms	32768kb
20-1	500ms	32768kb	5
20-2	500ms	32768kb