#P7066. Grave Placement in a Graveyard
Grave Placement in a Graveyard
Grave Placement in a Graveyard
Gerard is developing a Halloween computer game that is played on a rectangular graveyard which contains a rectangular chapel. During the game, the player attempts to place a new rectangular grave of given width and height within the graveyard. The grave must be completely inside the graveyard boundaries and must not overlap the chapel, although it may touch the boundaries of either the graveyard or the chapel.
The graveyard is defined as a rectangle with its bottom-left corner at (0, 0) and top-right corner at (w, h). Inside the graveyard, the chapel is given as a rectangle with its bottom-left corner at (x1, y1) and top-right corner at (x2, y2). You are also given the width and height of the grave to be placed. Determine whether there exists a placement for the grave such that:
- The entire grave is located within the graveyard, i.e. if the grave's bottom-left is at (gx, gy), then 0 ≤ gx and gx + grave_width ≤ w, and 0 ≤ gy and gy + grave_height ≤ h.
- The grave does not overlap with the chapel. (It is allowed to touch the chapel's borders.)
Note that the grave is axis-aligned and cannot be rotated. A valid placement may be completely to the left, right, above, or below the chapel if the dimensions allow, or any placement that avoids overlapping the chapel.
Formally, let the grave be placed with its bottom-left corner at (gx, gy). The grave placement is valid if and only if:
0 ≤ gx ≤ w - grave_width, 0 ≤ gy ≤ h - grave_height,
and at least one of the following holds:
- gx + grave_width ≤ x1 (grave completely to the left of the chapel)
- gx ≥ x2 (grave completely to the right of the chapel)
- gy + grave_height ≤ y1 (grave completely below the chapel)
- gy ≥ y2 (grave completely above the chapel)
Your task is to determine whether such a placement exists.
inputFormat
The input consists of three lines:
- The first line contains two integers w and h — the width and height of the graveyard.
- The second line contains four integers x1, y1, x2, y2 — the coordinates of the bottom-left and top-right corners of the chapel (with 0 ≤ x1 < x2 ≤ w and 0 ≤ y1 < y2 ≤ h).
- The third line contains two integers grave_width and grave_height — the dimensions of the new grave.
It is guaranteed that the chapel is strictly inside the graveyard.
outputFormat
Output a single line containing Yes
if it is possible to place the grave according to the conditions described above. Otherwise, output No
.
sample
15 15
5 5 10 10
3 3
Yes
</p>