Hockey

Interview

Time limit2sMemory limit128 MB

Summary
Count how many given points lie inside or on the boundary of a stadium shape formed by a rectangle and two semicircular ends.
Level

Easy3 of 10

Topics
Geometry, Implementation
Solved
No attempts yet

Problem

Minsik Corporation received an urgent request from the International Ice Hockey Federation (IIHF). They needed a system that sounds an alarm when too many players from the same team are on the rink. The system works in three steps.

  1. A digital camera takes a picture of the rink every second.
  2. The positions of all players are extracted from the picture.
  3. The number of players from the same team inside the hockey rink is computed.

The hockey rink is the union of a central rectangle and two circular end regions. The rectangle has lower-left corner (X, Y) and size W * H. Let r = H / 2. The left circle has center (X, Y + r), the right circle has center (X + W, Y + r), and both circles have radius r.

Given the players' coordinates, determine how many players are inside the rink or on its boundary.

Input

The first line contains integers W H X Y P. P is the number of players.

W and H are positive integers at most 100, and H is even. X and Y are integers whose absolute values are at most 100. P is a positive integer at most 50.

Each of the next P lines contains one player's coordinates x y. The absolute value of each coordinate is at most 300.

Output

Print the number of players who are inside the rink or on its boundary.

Examples4

  1. Example 1

    Input
    20 10 5 0 3
15 5
1 5
1 1
    Expected output
    2

  2. Example 2

    Input
    20 10 0 0 14
-5 5
-4 2
-4 8
-3 1
-3 9
0 0
0 10
20 0
20 10
23 1
23 9
24 2
24 8
25 5
    Expected output
    14

  3. Example 3

    Input
    52 84 -44 66 10
26 118
-33 106
-49 128
40 114
-10 101
47 85
25 142
-16 140
-82 126
7 145
    Expected output
    8

  4. Example 4

    Input
    24 100 -62 71 8
-63 109
-26 164
-9 91
-113 80
-124 75
-95 140
-89 116
-55 113
    Expected output
    6