PROBLEM STATEMENT
The owners of Parallelogram Fencing, Inc. have subcontracted you to determine
their minimum fencing requirements for a job. When a customer needs an area
fenced, they give the coordinates of certain objects which must be fenced in.
However, the fencers of Parallelogram Fencing cannot comprehend installing a
fence in anything other than a rectangle. Thus, it is your job, given a set of
coordinates, to find the minimum length of fence necessary to enclose all of
the coordinates.
Each coordinate is to be treated as a 1 unit by 1 unit square. So, a single
coordinate would require fencing in a square 1 unit by 1 unit, yielding a
perimeter of 4 units.
There may be multiple rectangular areas of fence, but no two may overlap or
intersect. That is, the same square may not be surrounded by two separate
lengths of fence. For example, it is not a valid solution to have one rectangle
covering squares 0,0 and 1,0, and another rectangle covering squares 1,0 and 1,1.
However, the edges of two separate rectangles may touch. (i.e., it is legal to
have on rectangle covering 0,0, and another covering 1,0). These edges touch,
and the rectangles do not overlap.
DEFINITION
Class name: Fencing
Method name: minCost
Parameters: String[]
Returns: int
Method signature (make sure it is declared public):
int minCost(String[] points);
points will consist of Strings formatted as "<int>,<int>". (Quotes and brackets
included for clarity only).
The Strings in points are not necessarily unique.
TopCoder will enforce the following restrictions:
* points will have between 1 and 20 elements, inclusive.
* each integer will be between 1 and 100, inclusive.
EXAMPLES
With parameters of {"0,0","0,1","1,1","2,3"} we have a layout which looks like
this: (an X is an object requiring fencing, and a - is a blank piece of ground).
X----
XX---
-----
--X--
-----
Taking the parameters in order, with one square ("0,0"), it clearly requires 4
units of fence to surround.
Adding the second square, directly below it, we see that we can now surround
the two by using only 6 units of fence.
Adding the third ups the fence requirement to 8, since we now have a 2x2 square
covering from (0,0) to (1,1).
The fourth parameter, being completely disjoint, should be placed in its own
rectangle and requires another 4 units of fence.
So, the minimum length of fence required for this is 12. One rectangle covers
from (0,0) to (1,1) and the other one covers only
(2,3). So, the layout looks as follows: ('F' is a fence, '-' is blank ground).
FF---
FF---
-----
--F--
-----
The perimeter of the first section is 8, and the perimeter of the second one is
4, yielding a total of 12.
minCost({"2,3","2,3","3,0","1,3"}) returns 10
minCost({"3,4","4,0","4,0","1,3"}) returns 12
minCost({"1,0","0,0","3,0","1,2","3,1","2,0"}) returns 14
minCost({"4,1","0,1","3,2","1,2","1,1","3,0","2,0","2,4","0,4","3,3","4,0","4,3"
,"0,1","2,2"}) returns 20