A Packing Problem
InterviewTime limit2sMemory limit512 MB
Given a rectangle and two circles, decide whether both circles fit inside the rectangle without overlapping, allowing tangency.
- Level
Medium6 of 10
- Topics
- Geometry, Math, Implementation, Brute force
- Solved
- No attempts yet
Problem
Miguel packs cans into boxes with a rectangular base. Every can is a right circular cylinder, and the two cans can have different heights. The height of the box is always greater than the height of either can.
Miguel wants to put two cans, whose radii may differ, into one box. The packing is good if both cans stand upright (looking into the box from above you see the two circular bases) and neither can sits on top of the other. Every other arrangement is bad. The two cans may touch each other on the sides, and a can may touch a wall of the box.
In other words, the packing is good exactly when both base circles lie inside the rectangular base of the box and the interiors of the two circles do not overlap. Two circles that meet at a single point do not count as overlapping.
Given the two side lengths of the base of the box and the radii of the two cans, decide whether a good packing exists.
Input
The first line contains the number of test cases .
Each of the next lines contains four integers , , , separated by single spaces. and are the side lengths of the base of the box, and and are the radii of the two cans to be packed.
Constraints
Output
For each test case, print PACKING GOOD on its own line if a good packing exists, and PACKING BAD otherwise.
Hint
The first test case of the first example can be packed like this.
