Lawn Mower

The International Collegiate Soccer Competition (ICSC) is famous for its well-kept rectangular stadiums. The grass playing fields in ICSC stadiums are always 100 meters long and 75 meters wide. The grass is mowed every week with special lawn mowers, always using the same strategy: first, they make a series of passes along the length of the field, and then they do the same along the width of the field. All passes are straight lines, parallel to the sides of the field.

Mowing along the length of the field

Mowing along the width of the field

The ICSC has hired a new lawn mower, Guido. Guido is very chaotic, and instead of covering the field incrementally, he likes to choose random starting positions for each of his passes. But he is afraid of not doing a good job and being fired by the ICSC, so he has asked you to help him. Write a program to make sure that the grass in the field is perfectly cut: all parts of the field have to be mowed at least once when the mower goes from end to end, and again when the mower goes from side to side.

Input Specification

Each test case contains 3 lines. The first line contains two integers, n_x (0 < n_x < 1 000) and n_y (0 < n_y < 1 000), and a real number w (0 < w ≤ 50), which represents the width of the cut of that particular lawn mower. The next line describes the end-to-end passes (along the length of the field), and contains n_x real numbers x_i (0 ≤ x_i ≤ 75) describing the starting positions of the mower's center in Guido's end-to-end passes. The last line describes the side-to-side passes, with n_y real numbers y_i (0 ≤ y_i ≤ 100).

The end of the test cases is signalled with a line that contains the numbers “0 0 0.0”. You should generate no output for this line, as it is not a test case.

Real numbers for w, x_i and y_i can have up to 7 digits after the decimal point, and any cut will also include its boundaries. For example, if a 2.0-meter-wide cut is performed along the 10.0-meter mark, then a strip of grass from 9.0 to 11.0 (including both) will be considered “cut”.

Output Specification

Print “YES” if Guido has done a good job, or “NO” if some part of the field has not been mowed at least once when the mower was travelling along the length of the field, and again when it was travelling along the width.

Note: The ICSC is sponsored by the Association for Sports Machinery (ASM), which started out in the US, so they prefer to use the term “soccer” instead of “football”.

Sample Input

1. 8 11 10.0
2. 0.0 10.0 20.0 30.0 40.0 50.0 60.0 70.0
3. 0.0 10.0 20.0 30.0 40.0 50.0 60.0 70.0 80.0 90.0 100.0
4. 8 10 10.0
5. 0.0 10.0 20.0 30.0 40.0 50.0 60.0 70.0
6. 0.0 10.0 30.0 40.0 50.0 60.0 70.0 80.0 90.0 100.0
7. 4 5 20.0
8. 70.0 10.0 30.0 50.0
9. 30.0 10.0 90.0 50.0 70.0
10. 4 5 20.0
11. 60.0 10.0 30.0 50.0
12. 30.0 10.0 90.0 50.0 70.0
13. 0 0 0.0

download as text file

Output for Sample Input

1. YES
2. NO
3. YES
4. NO

download as text file

Original Problem

Southwestern Europe Regional Contest, 2010