The Dutch Farmer

Time limit: 0.1s Memory limit: 4MB Input: Output:


Did you know? Tulips were so valuable in the 17th17^{th} century that they caused an economic phenomenon known as Tulip Mania - some bulbs were worth more than houses.

A field of tulips is represented as an axis-aligned rectangle, with irrigation sprinklers placed on its four sides. These sprinklers spray a fertilizing solution over the field.

The Dutch farmer, Jakob, wants to determine how many tulips will ripen faster because they are planted in a special fertilized zone.

There are NN tulips planted at locations (Xi, Yi)(X_i,\ Y_i) for i=0N1i=0\ldots N-1. A tulip is considered to be in the fertilized zone if, together with the four corners of the rectangle, it forms

  • two acute-angled triangles, and
  • two obtuse-angled triangles.

Your task is to count how many tulips meet this condition.

Input data

The input file consists of:

  • A line containing integers topLeftX\mathtt{topLeftX}, topLeftY\mathtt{topLeftY}.
  • A line containing integers topRightX\mathtt{topRightX}, topRightY\mathtt{topRightY}.
  • A line containing integers bottomRightX\mathtt{bottomRightX}, bottomRightY\mathtt{bottomRightY}.
  • A line containing integers bottomLeftX\mathtt{bottomLeftX}, bottomLeftY\mathtt{bottomLeftY}.
  • A line containing integer NN.
  • NN lines, the ii-th of which consisting of integers XiX_{i}, YiY_{i}.

Output data

The output file must contain a single line consisting of integer KK, the number of tulips in the special zone.

Constraints and clarifications

  • All points, including the rectangle's corners, lie within the geometric space [1 500,1 500][1 500,1 500][-1 \ 500, 1 \ 500] \cdot [-1 \ 500, 1 \ 500].
  • The rectangle is axis-aligned, that is, the sides of the rectangle are parallel to the axes.
  • 1N100 0001 \le N \le 100 \ 000.
  • All tulips are inside the rectangle. There is no tulip located on a side of the rectangle.
  • All tulip locations are unique (there are no identical (Xi, Yi)(X_i,\ Y_i) positions).
# Points Constraints
1 0 Examples
2 100 No additional constraints

Example 1

stdin

0 5
10 5
10 0
0 0
5
2 3
1 4
4 1
9 1
6 3

stdout

4

Explanation

In the following figures, the red\textcolor{red}{red} areas are covered with fertilizer, while the blue\textcolor{blue}{blue} areas are not.

In the first sample case, the only tulip outside the fertilized area is located at position (2, 3)(2,\ 3).

Example 2

stdin

0 35
35 35
35 0
0 0
10
17 8
16 5
32 27
18 32
8 18
17 30
14 19
5 11
2 32
2 11

stdout

4

Explanation

In the second sample case, the tulips inside the fertilized area are located at the points: (32, 27)(32,\ 27), (14, 19)(14,\ 19), (5, 11)(5,\ 11),
and (2, 32)(2,\ 32).

Log in or sign up to be able to send submissions!