DMPG '15 S2 - MMORPG

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Neptune is questing in a certain online role-playing game. The game is played on a tiled plane where each tile is a square of unit dimensions and (0,0) is defined as the top-left corner of the plane. This game has theme music that is unlocked when visiting the interior of any of the R rectangular regions in the game (one song per region). A region is defined by an (x, y) pair, the top left corner of a rectangle that is w-1 units wide and l-1 units long. Being on the edge of a rectangular region counts as visiting it. Each song may only be unlocked once.

This game also has the concept of magic, so Neptune will teleport N times to a given set of (x, y) coordinates.

How many songs will he unlock?

Input Specification

The first line will contain 2 space-separated integers R (0 \le R \le 10^3) and N (1 \le N \le 10^3).
The next R lines will each define a region where music may be unlocked as 4 space-separated integers x, y, w, and l (0 \le x,y; 1 \le x + w, y + l < 10^6).
Finally, the next N lines will each contain a pair of (x, y) coordinates: the locations Neptune will teleport to in chronological order.

Output Specification

The number of songs Neptune will unlock, on one line.

Sample Input

2 1
0 0 100 100
0 0 50 50
60 60

Sample Output

1

Comments