TopCoder problem "PackingShapes" used in SRM 270 (Division I Level Three)



Problem Statement

    

Little Timmy has a rectangular frame and several shapes cut out from cardboard. He tries to fit each of the shapes into the frame (one shape at a time). Sometimes the piece fits easily, sometimes it is clear that the shape is too big to fit... and sometimes Timmy just doesn't know. Then he always comes to ask you for help.

You decided to write a program that will answer Timmy's questions.

You will be given the width and height of the frame and a String[] shapes describing Tommy's shapes. Each of the shapes is either a circle or a rectangle. Each element of shapes is of the one of the following forms:

  • "CIRCLE RADIUS", where RADIUS is the radius of the circle.
  • "RECTANGLE WIDTH LENGTH", where WIDTH and LENGTH are the dimensions of the rectangle.

Your method is supposed to return a String[] results, where the i-th element of results is "YES" or "NO", depending on whether the i-th shape fits into the empty frame.

 

Definition

    
Class:PackingShapes
Method:tryToFit
Parameters:int, int, String[]
Returns:String[]
Method signature:String[] tryToFit(int width, int height, String[] shapes)
(be sure your method is public)
    
 

Notes

-The shapes may be rotated arbitrarily.
-The shapes may touch the frame, and they may even have a common part of the boundary.
 

Constraints

-width and height are between 1 and 1000, inclusive.
-shapes contains between 1 and 50 elements, inclusive.
-Each element of shapes is of one of the following forms:
  • "CIRCLE RADIUS"
  • "RECTANGLE WIDTH LENGTH"
-All numbers in shapes are integers between 1 and 1000, inclusive, with no leading zeroes.
 

Examples

0)
    
100
100
{"RECTANGLE 3 3", 
 "RECTANGLE 3 230",
 "RECTANGLE 140 1"}
Returns: {"YES", "NO", "YES" }
The first rectangle clearly fits, but the second one clearly doesn't. The third one can be placed inside the frame after it is rotated 45 degrees.
1)
    
100
100
{"RECTANGLE 100 100",
 "CIRCLE 50"}
Returns: {"YES", "YES" }
Touching the frame is allowed.
2)
    
10
100
{"RECTANGLE 99 9",
 "CIRCLE 22"}
Returns: {"YES", "NO" }
The rectangle can be rotated, but the circle is too large.
3)
    
170
900
{"RECTANGLE 200 700",
 "RECTANGLE 3 910",
 "RECTANGLE 1000 7",
 "CIRCLE 5",
 "CIRCLE 50",
 "CIRCLE 500",
 "RECTANGLE 1000 99"}
Returns: {"NO", "YES", "NO", "YES", "YES", "NO", "NO" }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8067&pm=4751

Writer:

misof

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Geometry