Problem Statement |
| As an architect you want to design a building. It will consist of n boxes,
stacked one on top of another (ok, you are not much of an architect). The boxes will
each have a vertical height of 10, have the same ratio of width to length, all be
oriented the same way, and
have their centers on the same verical line (the elevator shaft).
The bottom box will have its bottom exactly
fill the rectangular building lot which has a given width and length.
So your design decision is just to decide on the sizes of the n boxes.
Structural integrity provides some constraints on your design. The support area
of a box (other than the bottom box) is defined to be the common area between it
and the box below it. The following 2 rules must be satisfied. -
The "overhang" rule" says that no point on the bottom of a box may be more
than a distance of 50 from the box's support area. Here the crucial distance
is the distance between a bottom corner of a box and the corresponding upper
corner of a smaller box on which it rests.
-
The "strength rule" says that each box's support area must be big enough to
support the volume of the box (its width times its length times 10) and of all the boxes above it. The total volume
that can be supported by an area is K*area. The strength rule does not apply
to the bottom box which rests on the ground.
Here is a side view of a building made of 4 boxes. The X box must be supported
by the area of the top of Y. The total of the volumes of X and Y must be
supported by the area at the bottom of Y. The total of the X,Y, and Z volumes
must be supported by the area at the top of Q. X must not overhang Y by more than 50,
and Z must not overhang Q by more than 50.
XXXXX
YYY
ZZZZZZZZZZZZZ
QQQQQQQQQQQ
Our design goal is to make the top floor (the roof) have as large an area as
possible for our helipad and roof gardens. It may even be larger than our lot.
Create a class Architect that
contains a method roofArea that is given width, length, n, and K and that
returns the area of the largest roof possible. Return -1 if no building meets
all the requirements.
|
|
Definition |
| Class: | Architects | Method: | roofArea | Parameters: | int, int, int, int | Returns: | double | Method signature: | double roofArea(int width, int length, int n, int K) | (be sure your method is public) |
|
|
|
|
Notes |
- | Your return value must have an absolute or relative error less than 1e-9. |
|
Constraints |
- | width and length will be between 1 and 5000, inclusive. |
- | n will be between 1 and 100, inclusive. |
- | K will be between 1 and 10000, inclusive. |
|
Examples |
0) | |
| | Returns: -1.0 |
This building has just 2 boxes. The only support requirement is that the
area between them must be enough to support the volume of the top box. But
K is so low that the area of the bottom of a box cannot support its own volume,
so no building meets the requirements.
|
|
|
1) | |
| | Returns: 1000000.0 |
This building is a single box, supported by the ground. Its size must be
1000 x 1000 to match the width and length of the lot.
|
|
|
2) | |
| | Returns: 5808.0 |
Here the overhang rule determines the size of the top box. The horizontal
distance from the center to a corner of the bottom box is 5. So the top
box can have its corner 55 from the center. So it can be 11 times as big
linearly, and its area would then be 11*11*(6*8) = 5808. K is large enough
so that the support area of 48 can support the 58080 volume of the top box.
|
|
|
3) | |
| | Returns: 52489.99599679679 |
The design is (approximately) 100 x 200 = 20,000 on the bottom,
117.28 x 234.56 = 27,510 in
the middle, and 162 x 324 = 52,490 on top. The bottom box can then just
barely support the top 2 boxes,
since their volume is 10*27,510 + 10*52,490 = 800,000 which requires a
support area of 800,000/40 = 20,000. The top box is easily supported by
the box under it, but just barely satisfies the overhang rule. The horizontal
distance from the center to one of its corners is 131.125 while the distance
from the center to a corner of the top box is 181.125, an overhang of 50. |
|
|