TopCoder problem "TurfRoller" used in SRM 203 (Division I Level Three)



Problem Statement

    

Warning: This problem statement contains images that may not be visible to plugin users. For best results, use the standard Arena editor.

Raccoons dug up your lawn during the spring, but now they've agreed to resurface it for a modest fee. They come equipped with a turf roller and a truckload of rectangular turf strips of fixed dimensions. We say that "length" is the measure of a turf strip's longer edges, while "breadth" is the measure of its shorter edges. Your lawn is also rectangular: from a bird's-eye view, what we call "width" is the distance from its left border to its right border, and "height" is the distance from bottom to top.

For aesthetic reasons, you demand that the turf be laid at a certain angle. This angle is between 0 and 90 degrees, inclusive, and is measured counterclockwise from the bottom border of your lawn. In other words, the raccoons will ensure that the longer edges of every turf strip are inclined at precisely this angle relative to the horizontal axis.

It may well happen that a single turf strip laid at the desired angle is not long enough to span your lawn. In such cases, the raccoons lay several turf strips end to end, precisely aligning the shorter edges of subsequent strips. At no time will turf strips overlap. Any scraps of turf that overhang the lawn's borders are immediately trimmed off and discarded. Once the raccoons have completed their labors, the entirety of your lawn will be covered with fresh turf.

You are given five integers that respectively state: the width of your lawn; the height of your lawn; the angle at which turf is to be laid; the length of each turf strip; and the breadth of each turf strip. Calculate the minimum number of turf strips that the raccoons must use in the course of resurfacing your lawn.

 

Definition

    
Class:TurfRoller
Method:stripNum
Parameters:int, int, int, int, int
Returns:int
Method signature:int stripNum(int lawnWidth, int lawnHeight, int stripAngle, int stripLength, int stripBreadth)
(be sure your method is public)
    
 

Notes

-Turf strips must always be laid lengthwise, as in the illustrations below. Breadthwise orientation is not permitted.
-Each turf strip must be laid at the specified angle, even if a different angle would allow the whole lawn to be covered with a single piece.
 

Constraints

-lawnWidth is between 1 and 100, inclusive
-lawnHeight is between 1 and 100, inclusive
-stripAngle is between 0 and 90, inclusive
-stripLength is between 1 and 100, inclusive
-stripBreadth is between 1 and 100, inclusive
-stripBreadth is less than or equal to stripLength
-If the angle is not 0 or 90, then the input is such that the final result will not be affected by small precision errors in your intermediate calculations. Specifically, the result would remain the same if both the length and width of the lawn were greater by 0.1 or less by 0.1 than they are in the input.
 

Examples

0)
    
60
90
39
60
25
Returns: 8


This diagram shows that the raccoons can resurface a lawn of width 60 and height 90 by laying as few as eight turf strips, each of length 60 and breadth 25, at an angle of 39 degrees.

1)
    
26
6
38
20
14
Returns: 2


In an optimal configuration, the upper edge of the top left turf strip doesn't necessarily intersect with the top left corner of the lawn.

2)
    
8
9
0
3
3
Returns: 9
Here, the strips are laid horizontally.
3)
    
6
4
45
10
10
Returns: 1
4)
    
2
3
45
2
1
Returns: 6
5)
    
70
70
45
76
24
Returns: 6
6)
    
100
100
45
2
1
Returns: 5112

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2247

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5849&pm=2247

Writer:

Eeyore

Testers:

lbackstrom , brett1479

Problem categories:

Geometry