TopCoder problem "SuperPasture" used in TCHS SRM 32 (Division I Level Three)



Problem Statement

    

Farmer Brown has many rectangular pastures. Two pastures are connected if they share a border (two pastures which share a corner are not connected). A super pasture is a maximal connected set of pastures. In other words, for every two pastures in a super pasture there exists a continuous path which connects these 2 pastures and never leaves the super pasture. If a pasture is not connected with any other pasture, it is considered to be a super pasture itself. 

   0123456789
   ----------
 0|.........5
 1|.00..11277
 2|.00..11277
 3|.00....2..
 4|...66..233
 5|.88664....
 6|...664....

The diagram above contains 9 pastures, which form 3 super pastures. Pasture 0 does not share borders with any other pasture, and forms a super pasture itself. Pastures 1, 2, 3, 5 and 7 form another super pasture, while pastures 4, 6 and 8 form the third super pasture. Please note that pastures 0 and 6 are not connected because they share only a corner.

The badness of a super pasture is the area of its bounding rectangle minus the sum of the areas of its pastures. For example, if a super pasture is formed by only 1 pasture, it has a badness of 0. The super pastures in the diagram have badnesses of 0, 10 and 5, respectively.

Farmer Brown has decided to sell one of his pastures. To choose the pasture he will sell, farmer Brown has the following rules:

  1. The pasture must belong to the super pasture with the highest badness. If several super pastures have the maximal badness, he can choose a pasture from any of them.
  2. Selling the pasture must not break a super pasture apart.
  3. Among the pastures which satisfy the first two conditions, he will choose the pasture with the smallest area. In case of a tie, he will choose the pasture with the lowest index.
See the examples for further clarification.

You will be given a String[] pastures containing the information about all of farmer Brown's pastures. Each element of pastures will be formatted like "a b c d", where a, b, c and d will represent the leftmost, the rightmost, the topmost and the bottommost coordinates of the pasture, respectively. In other words, the pasture is a rectangle with two corners at (a, c) and (b, d). Your program should return the 0-based index of the pasture farmer Brown will sell.

 

Definition

    
Class:SuperPasture
Method:whichOne
Parameters:String[]
Returns:int
Method signature:int whichOne(String[] pastures)
(be sure your method is public)
    
 

Constraints

-pastures will contain between 1 and 50 elements, inclusive.
-Each element in pastures will be formatted as "a b c d", where a, b, c and d will be integers between 0 and 1000, inclusive.
-In each element of pastures, a will be strictly less than b, and c will be strictly less than d.
-Each number in each element of pastures will not contain extra leading zeroes.
-No two pastures will intersect.
 

Examples

0)
    
{"1 3 1 4", "5 7 1 3", "7 8 1 5", "8 10 4 5", "5 6 5 7", "9 10 0 1", "3 5 4 7", "8 10 1 3", "1 3 5 6"}
Returns: 5
The example from the problem statement. Applying the rules:
  1. The super pastures have badnesses of 0, 10 and 5, respectively; therefore, farmer Brown chooses the second super pasture.
  2. Selling a pasture must not break the corresponding super pasture apart, so he can not sell pastures 2 and 7 (also, he can not sell pasture 6, but it does not belong to the chosen super pasture anyway).
  3. Farmer Brown must choose between pastures 1, 3 and 5. These pastures have areas of 4, 2 and 1, respectively; therefore, he sells pasture 5.
1)
    
{"4 6 1 5", "1 6 5 7", "8 13 1 3", "8 10 3 7"}
Returns: 0
Notice there are two super pastures. Both super pastures have the same badness. Also notice that pastures 0 and 3 are the smallest and their areas are also equal; therefore, the pasture with the lower index is chosen. 

   0123456789012
   -------------
 0|.............
 1|....00..22222
 2|....00..22222
 3|....00..33...
 4|....00..33...
 5|.11111..33...
 6|.11111..33...
2)
    
{"0 100 0 100", "500 511 500 509", "710 720 710 720"}
Returns: 1
Each of three pastures forms a super pasture with the badness of 0. Therefore, farmer Brown chooses the super pasture with the smallest area.
3)
    
{"0 1 1 2", "0 1 2 3", "0 1 3 4", "0 1 0 1"}
Returns: 2
Farmer Brown can sell pastures 2 or 3, so he chooses the one with the lower index.
4)
    
{"0 1 1 2", "0 1 2 3", "0 2 3 4", "0 1 0 1"}
Returns: 3
The situation is similar to the previous example, but now the areas of pastures 2 and 3 are not equal.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6868

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10656&pm=6868

Writer:

Uranium-235

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force, Search, String Parsing