ZOJ Problem Set - 3042
The government decides to build some cities in a newly developping area. Now this area is divided into several pieces of blocks. The block length is 1 and they are represented by rectangular coordinates. They have M different locations to select from, while there are N factories which have been built in this newly developping area. All the cities can be regarded as a block. If we say the i-th city is located on (x, y), it means that this city occupies the whole block of (x, y) (occupies All the points with x-cord between [x, x + 1] and y-cord between [y, y + 1] ). All the factories can be regarded as a point, and what you know is only the block which it is located in but not the accurate position. In addition, there is at most one factory in a block.
As we know, the fog from the factory will pollute the city heavily. Nowadays, thanks to the new invention, we can prevent the wind from all directions to bring the pollution to other areas except the direction shown in the following picture.
Now it's your job to choose all the city locations that will never get pollution by the factories. Note: if the pollution can only affect the corner of a city, we can assume that this city gets no pollution.
The first line of a input block contains the numbers N, M (1 <= N, M <= 100000). Line 2 ~ N + 1 will each contains two integers(x, y) the location of a block which a factory is located on. Line N + 2 ~ M + N + 1 will each contains two integers (x, y) the location of a city. The x and y coordinates of the locations will be between -10000000 and 10000000, inclusive.
The first line of your output block should be an integer K representing the number of city locations which the government can choose from. The next K lines should contain the coordinates of the cities. The coordinates should be sorted in ascending order of x coordinates, and in case of tie, ascending order of y coordinates.
3 2 -1 2 -1 10 1 -2 0 0 0 10 2 2 -1 2 1 -2 0 0 0 10
0 1 (0,10)
Author: MO, Luyi
Source: ZOJ Monthly, September 2008