Statistics

Problem Statement for "Architects"

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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 1000

    1000

    100

    10000

    Returns: 3.457271320057437E7

  6. 1

    1

    100

    11

    Returns: 3.944304526105059E-31

  7. 10

    10

    10

    300

    Returns: 2287.3635709236396

  8. 10

    10

    1

    10

    Returns: 100.0

  9. 10

    10

    2

    10

    Returns: 100.0

  10. 5000

    5000

    3

    10

    Returns: -1.0

  11. 5000

    5000

    100

    10

    Returns: -1.0

  12. 1

    1

    10

    11

    Returns: 5.131581182307066E-9

  13. 1

    1

    100

    11

    Returns: 3.944304526105059E-31

  14. 4999

    3

    10

    75

    Returns: 13575.230351140042

  15. 1

    1

    100

    10000

    Returns: 906.6044494080761

  16. 5000

    4999

    100

    10000

    Returns: 1.4399656894988048E8

  17. 5000

    5000

    100

    10000

    Returns: 1.440085713374673E8

  18. 17

    111

    7

    12

    Returns: 0.29120370370370363

  19. 1162

    3599

    62

    2667

    Returns: 2.8552464655759886E7

  20. 3843

    250

    54

    3415

    Returns: 5424808.2075312305

  21. 3127

    553

    39

    2633

    Returns: 8344037.218917707

  22. 2761

    3006

    99

    3482

    Returns: 7.078527407258719E7

  23. 4572

    4883

    76

    3860

    Returns: 1.0045066826889175E8

  24. 2603

    2074

    35

    1348

    Returns: 2.206269237523116E7

  25. 3312

    620

    81

    714

    Returns: 4502116.1450331565

  26. 1789

    3753

    6

    7054

    Returns: 8426130.173917074

  27. 4874

    4846

    14

    1854

    Returns: 3.3399280047233723E7

  28. 1315

    3333

    61

    9458

    Returns: 3.1352029624960594E7

  29. 3957

    1222

    91

    6432

    Returns: 4.868859296954085E7

  30. 3646

    587

    49

    170

    Returns: 587352.8191156008

  31. 3694

    114

    51

    9557

    Returns: 2331360.817861364

  32. 4709

    3027

    95

    9317

    Returns: 1.0231603615957418E8

  33. 347

    2169

    90

    8645

    Returns: 1.8006254753502868E7

  34. 670

    1254

    75

    5970

    Returns: 2.0525545577459134E7

  35. 2035

    4302

    82

    8167

    Returns: 6.3916590328182146E7

  36. 4556

    4774

    31

    9683

    Returns: 4.602114915307121E7

  37. 2754

    1629

    15

    166

    Returns: 7247602.338271659

  38. 3727

    368

    74

    4331

    Returns: 1.1929328990457427E7

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.
This problem was used for: