Architects | Topcoder Archive

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

```
1000
```
```
1000
```
```
2
```
```
5
```
```
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.
```
1000
```
```
1000
```
```
1
```
```
5
```
```
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.
```
6
```
```
8
```
```
2
```
```
3000
```
```
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.
```
100
```
```
200
```
```
3
```
```
40
```
```
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.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.