|
|
SPOJ Problem Set (classical)
347. Lazy Cows
Problem code: LAZYCOWS
|
Farmer John regrets having applied high-grade fertilizer to his
pastures since the grass now grows so quickly that his cows no
longer need to move around when they graze. As a result, the cows
have grown quite large and lazy... and winter is approaching.
Farmer John wants to build a set of barns to provide shelter for
his immobile cows and believes that he needs to build his barns
around the cows based on their current locations since they won't
walk to a barn, no matter how close or comfortable.
The cows' grazing pasture is represented by a 2 x B (1 <= B <=
15,000,000) array of cells, some of which contain a cow and some
of which are empty. N (1 <= N <= 1000) cows occupy the cells in
this pasture:
-------------------------------------------------------
| | cow | | | | cow | cow | cow | cow |
-------------------------------------------------------
| | cow | cow | cow | | | | | |
-------------------------------------------------------
Ever the frugal agrarian, Farmer John would like to build a set of
just K (1 <= K <= N) rectangular barns (oriented with walls parallel
to the pasture's edges) whose total area covers the minimum possible
number of cells. Each barn covers a rectangular group of cells in
their entirety, and no two barns may overlap. Of course, the barns
must cover all of the cells containing cows.
By way of example, in the picture above if K=2 then the optimal
solution contains a 2x3 barn and a 1x4 barn and covers a total of
10 units of area.
Input
The first line of the input contains integer t representing the number of test cases. Then t cases follow. Each case has the following form:
- Line 1: Three space-separated integers, N, K, and B.
- Lines 2..N+1: Two space-separated integers in the range (1,1) to
(2,B) giving the coordinates of the cell containing each cow.
No cell contains more than one cow.
Output
For each test case, output the minimum area required by the K barns in order to cover
all of the cows.
Example
Input:
1
8 2 9
1 2
1 6
1 7
1 8
1 9
2 2
2 3
2 4
Output:
10
Input details:
As pictured above.
Output details:
As discussed above.
| Added by: | Ngô Minh Ðức |
| Date: | 2005-05-03 |
| Time limit: | 9s
|
| Source limit: | 50000B |
| Languages: | All except: ERL JS PERL 6 |
| Resource: | US Open International 2005 Gold Division |
|
|
|
|
RSS