HARDQ - Hard Question

no tags 

Students of computer science in Bratislava enjoy hiking and camping during their long summer breaks. They love walking silently in the groves, visiting sparkling waterfalls, exploring dark caves, climbing steep hills, or just sleeping in a tent. Some of them already visited all the national parks in Slovakia and nearby countries.

With no more new national parks to visit, frustrated students decided to set up a new national park (NP) by themselves. After long arguing, they finally agreed on the boundary of the NP. Now they want to purchase all the land needed for NP from present owners. Their funds are limited (after all, they are only students), therefore they do not want to buy any land outside the NP.

The NP can be described as a polygon with N vertices. There is a set P of M rectangular plots of land available for sale by their owners. The rectangles are mutually disjoint and axis-parallel. Your task is to decide whether it is possible to purchase subset of plots P exactly covering the proposed NP.


Input file consists of several test cases separated by a blank line. Each test case starts with two integers N and M. Next N lines contain the coordinates of the vertices of the NP. Each of the following M lines describes one plot. For each plot, the coordinates of two opposite corners of the rectangle are given. The values N=0, M=0 end the input and should not be processed. [N, M <= 3000]


For each test case output either 'YES' or 'NO' depending on whether it is possible to set up the NP using P or not.


4 2
0 0
0 2
2 2
2 0
1 0 0 2
1 0 2 2

3 1
0 0
2 2
2 0
0 0 1 1

0 0


hide comments
Brian Bi: 2024-01-08 02:01:41

In the test data from the IPSC, all coordinates are less than or equal to 10,000 in absolute value. Hopefully that's also true in the SPOJ test data.

Gaurav Mittal: 2011-07-28 15:07:05

you should specify the maximum value of the co-ordinates

Added by:Roman Sol
Time limit:5s
Source limit:30000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:IPSC 2004