Connection Status:
Competition Arena > PackingShapes

PackingShapes

SRM 270 · 2005-11-03 · by misof

SRM 270 · 2005-11-03 · by misof · Geometry
Class Name: PackingShapes
Return Type: String[]
Method Name: tryToFit
Arg Types: (int, int, vector<string>)
Problem Statement

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.

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" }
4)
1
1
{"RECTANGLE 1 1", "RECTANGLE 2 1", "RECTANGLE 1 2", "RECTANGLE 2 2", "RECTANGLE 1 3", "RECTANGLE 2 3", "RECTANGLE 3 3", "CIRCLE 1", "CIRCLE 2", "CIRCLE 3", "RECTANGLE 1000 1000", "CIRCLE 1000"}
Returns: {"YES", "NO", "NO", "NO", "NO", "NO", "NO", "NO", "NO", "NO", "NO", "NO" }

Submissions are judged against all 93 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PackingShapes with a public method vector<string> tryToFit(int width, int height, vector<string> shapes) · 93 test cases · 2 s / 256 MB per case

Submitting as anonymous