The maximum area
All submissions for this problem are available.
Porto is blessed with a beautiful city park. The
park, in the western section of the city, borders the
Atlantic Ocean. It has great lawns, small forests,
plenty of flowerbeds, a variety of ponds, and, in
all, lots of points of interest. Porto families love
the park and flock to in on weekends and holidays.
With such multitudes, it is hard work to keep
the lawns in good shape. In order to control
the movements of the crowd, the engineers of the
municipality designed a system of paths connecting
points of interest. These paths are built with large
rectangular shale stones from the nearby Milhária quarry. Using sophisticated location
systems, the engineers were able to lay the stones perfectly aligned with the north-south
direction (and hence also with the east-west direction). Stones linking one from one point
of interest to another touch each other, forming a contiguous stoned surface, and do not
touch any stones belonging to any other stoned surface.
The “defend our park” movement wants to stage a demonstration in the park to publicise
their cause. Since they do not want to harm the lawns, they must stage the demonstration
in one of those stoned surfaces. In order to summon as many supporters as possible, but
not too many, they need to find out the area of the stoned surface with largest area.
Given the locations and dimensions of stones in the park, compute the area of the stoned
surface with the largest area.
The first line contains one positive integer, N, representing the number of rectangular
stones. N lines follow, each one describing the location and dimensions of a stone, by four
integers, X, Y , W, H, where (X Y ) are the coordinates of the location of the lower left
corner the stone, W is its length along the x-axis, and H is its length along the y-axis.
Sample Test cases
0 < N<=50 000 Number of stones.
0 < W <= 5000 0< H<= 500 Dimensions of stones.
It is guaranteed that, for the given inputs, the coordinates of the stone corners can be handled using normal 32-bit signed integers, as well as the total area of any stoned surface.
For every pair of distinct stones, the area of the intersection of the two rectangles that
represent them in the park is zero (i.e., there are no overlaps).
A single line with an integer: the area of the stoned surface with largest area.
14 1 2 2
16 9 1 5
11 3 5 2
3 4 2 5
5 9 3 2
21 3 2 8
13 2 1 1
13 8 3 5
|Time Limit:||- 1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.