ZOJ Problem Set - 3041
The government decided to build some cities in a newly developping area. Now they had N different locations to select from, while there were M factories in this newly developping area.The area was blowing northwest wind, so if we choose a location that located on the southeast quadrant of one of the factory (including the boundary), the fog from the factory would pollute the city heavily.
Now it's your job to choose all the city locations that will not get pollution by the factories.
The first line of a input block contains the numbers N, M (1 <= N, M <= 200000). Line 2 ~ N + 1 will each contain two integers(x, y) the location of a city. Line N + 2 ~ M + N + 1 will each contains two integers(x, y) the location of a factory. The x and y co-ordinates of the locations will be between -1000000000 and 1000000000, inclusive. There're no more than 10 test cases in the input data.
The first line of your output block should be an integer K represent the number of city locations which the government can choose from. The next K lines should contain the co-ordinates of the cities. The co-ordinates should be sorted in ascending order of x co-ordinates, and in case of tie, ascending order of y co-ordinates.
3 3 0 1 -2 2 1 3 -2 2 2 0 4 4
1 1 3
Author: OUYANG, Jialin
Source: ZOJ Monthly, September 2008