Battleship
Time limit2sMemory limit256 MB
Decide whether three axis-aligned rectangles (rotatable, non-overlapping) fit inside an A x B rectangle.
- Level
Medium7 of 10
- Topics
- Geometry, Brute force, Greedy, Implementation
- Solved
- No attempts yet
Problem
Petya and Vasya play battleship with slightly modified rules. Vasya has lost ten games in a row and does not intend to lose again. He analyzed Petya's battle tactics and found a serious flaw in them (or at least he very much hopes so). It turned out that on the field there is an rectangle of cells that Petya never fired at during all ten games. So Vasya decided to take his three largest ships and place them in this rectangle.
Vasya's plans are far-reaching, of course, but first he has to deal with some minor problems. For example, he needs to find out whether he can place his three ships so that they fit entirely inside the given rectangle. By the rules, ships are rectangles that must be placed parallel to the sides of the field. Ships may be rotated 90 degrees. Ships may touch each other, but they must not share any cell of the field.
Input
The first line contains an integer (), the number of tests. Each test consists of 4 lines. The first of them contains two integers and (), the dimensions of the rectangle in which the ships must be placed. The next three lines contain two integers each, and (), the dimensions of the -th ship.
Output
Print lines, the answers to the tests from the input. For each test, print Yes if the ships can be placed and No otherwise.