2014
02-14

# Doors And Preguins

The organizers of the Annual Computing Meeting have invited a number of vendors to set up booths in a large exhibition hall during the meeting to showcase their latest products. As the vendors set up their booths at their assigned locations, they discovered that the organizers did not take into account an important fact—each vendor supports either the Doors operating system or the Penguin operating system, but not both. A vendor supporting one operating system does not want a booth next to one supporting another operating system.

Unfortunately the booths have already been assigned and even set up. There is no time to reassign the booths or have them moved. To make matter worse, these vendors in fact do not even want to be in the same room with vendors supporting a different operating system.

Luckily, the organizers found some portable partition screens to build a wall that can separate the two groups of vendors. They have enough material to build a wall of any length. The screens can only be used to build a straight wall. The organizers need your help to determine if it is possible to separate the two groups of vendors by a single straight wall built from the portable screens. The wall built must not touch any vendor booth (but it may be arbitrarily close to touching a booth). This will hopefully prevent one of the vendors from knocking the wall over accidentally.

There are multiple cases (no more than 100).

The input consists of a number of cases. Each case starts with 2 integers on a line separated by a single space: D and P, the number of vendors supporting the Doors and Penguins operating system, respectively (1 <= D, P <= 500). The next D lines specify the locations of the vendors supporting Doors. This is followed by P lines specifying the locations of the vendors supporting Penguins. The location of each vendor is specified by four positive integers: x1, y1, x2, y2. (x1, y1) specifies the coordinates of the southwest corner of the booth while (x2, y2) specifies the coordinates of the northeast corner. The coordinates satisfy x1 < x2 and y1 < y2. All booths are rectangular and have sides parallel to one of the compass directions. The coordinates of the southwest corner of the exhibition hall is (0,0) and the coordinates of the northeast corner is (15000, 15000). You may assume that all vendor booths are completely inside the exhibition hall and do not touch the walls of the hall. The booths do not overlap or touch each other.

The end of input is indicated by D = P = 0.

There are multiple cases (no more than 100).

The input consists of a number of cases. Each case starts with 2 integers on a line separated by a single space: D and P, the number of vendors supporting the Doors and Penguins operating system, respectively (1 <= D, P <= 500). The next D lines specify the locations of the vendors supporting Doors. This is followed by P lines specifying the locations of the vendors supporting Penguins. The location of each vendor is specified by four positive integers: x1, y1, x2, y2. (x1, y1) specifies the coordinates of the southwest corner of the booth while (x2, y2) specifies the coordinates of the northeast corner. The coordinates satisfy x1 < x2 and y1 < y2. All booths are rectangular and have sides parallel to one of the compass directions. The coordinates of the southwest corner of the exhibition hall is (0,0) and the coordinates of the northeast corner is (15000, 15000). You may assume that all vendor booths are completely inside the exhibition hall and do not touch the walls of the hall. The booths do not overlap or touch each other.

The end of input is indicated by D = P = 0.

3 3
10 40 20 50
50 80 60 90
30 60 40 70
30 30 40 40
50 50 60 60
10 10 20 20
2 1
10 10 20 20
40 10 50 20
25 12 35 40
0 0

Case 1: It is possible to separate the two groups of vendors.

Case 2: It is not possible to separate the two groups of vendors.

1. 很多年以后，面对要罢免他的股东大会，王石应该会想起，2008恒大上市失败后资金链断裂，许家印登门求助的场景。那一次，王石没有提供任何帮助。

2. 既然说到动漫倒不如顺便看看《尸鬼》，人类在反侵略的过程中往往会变成比侵略者更可怕的怪物，我爱我的国家，但我不爱这怨声载道的社会

3. 既然说到动漫倒不如顺便看看《尸鬼》，人类在反侵略的过程中往往会变成比侵略者更可怕的怪物，我爱我的国家，但我不爱这怨声载道的社会

4. 既然说到动漫倒不如顺便看看《尸鬼》，人类在反侵略的过程中往往会变成比侵略者更可怕的怪物，我爱我的国家，但我不爱这怨声载道的社会

5. 既然说到动漫倒不如顺便看看《尸鬼》，人类在反侵略的过程中往往会变成比侵略者更可怕的怪物，我爱我的国家，但我不爱这怨声载道的社会

6. 既然说到动漫倒不如顺便看看《尸鬼》，人类在反侵略的过程中往往会变成比侵略者更可怕的怪物，我爱我的国家，但我不爱这怨声载道的社会

7. 既然说到动漫倒不如顺便看看《尸鬼》，人类在反侵略的过程中往往会变成比侵略者更可怕的怪物，我爱我的国家，但我不爱这怨声载道的社会

8. 既然说到动漫倒不如顺便看看《尸鬼》，人类在反侵略的过程中往往会变成比侵略者更可怕的怪物，我爱我的国家，但我不爱这怨声载道的社会

9. 既然说到动漫倒不如顺便看看《尸鬼》，人类在反侵略的过程中往往会变成比侵略者更可怕的怪物，我爱我的国家，但我不爱这怨声载道的社会

10. 既然说到动漫倒不如顺便看看《尸鬼》，人类在反侵略的过程中往往会变成比侵略者更可怕的怪物，我爱我的国家，但我不爱这怨声载道的社会

11. 既然说到动漫倒不如顺便看看《尸鬼》，人类在反侵略的过程中往往会变成比侵略者更可怕的怪物，我爱我的国家，但我不爱这怨声载道的社会

12. 既然说到动漫倒不如顺便看看《尸鬼》，人类在反侵略的过程中往往会变成比侵略者更可怕的怪物，我爱我的国家，但我不爱这怨声载道的社会

13. 既然说到动漫倒不如顺便看看《尸鬼》，人类在反侵略的过程中往往会变成比侵略者更可怕的怪物，我爱我的国家，但我不爱这怨声载道的社会

14. 既然说到动漫倒不如顺便看看《尸鬼》，人类在反侵略的过程中往往会变成比侵略者更可怕的怪物，我爱我的国家，但我不爱这怨声载道的社会

15. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。

16. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge