An Animal Contest 4 P3 - Snowy Slopes

View as PDF

Submit solution

Points: 10
Time limit: 2.0s
Memory limit: 256M

Problem type

The Alpine Acres Crest ski company wants to decide where to build its new exclusive Christmas ski slope! The area that the company owns can be modelled as an infinite 2-dimensional vertical plane.

Moreover, the skiing company has already built N potential endpoints for the ski slopes at points (x_i, y_i) where x_i represents the horizontal distance from the origin and y_i represents the vertical distance.

In addition to having built N potential endpoints, the company also surveyed eager skiers to see what steepness they prefer. The results of the surveys showed that there were M steepnesses that were popular, with the i-th steepness being represented with the integers k_i and d_i.

Being the company's loyal planner, you are tasked with finding the number of pairs of endpoints that can be possible slopes. Two points are a possible slope if there is at least 1 popular steepness i such that the two points form a line with a gradient equal to \frac{k_i}{d_i}.

The gradient of a line joined by two points (x_1, y_1) and (x_2, y_2) is equal to \frac{y_2 - y_1}{x_2 - x_1}.


2 \le N \le 10^5

1 \le M \le 20

1 \le x_i, y_i \le 10^9

-10^9 \le k_i, d_i \le 10^9

All x_i are distinct.

All y_i are distinct.

Neither k_i nor d_i will be 0.

Input Specification

The first line contains two space-separated integers N and M, the number of possible endpoints and the number of steepnesses respectively.

The next N lines contain two integers x_i and y_i, the coordinates of the i-th point.

The final M lines contain two integers k_i and d_i, the i-th preferred steepness.

Output Specification

Output one integer, the number of pairs of endpoints that can be possible slopes.

Sample Input

3 4
1 2
4 4
7 1
-1 1
2 1
4 6
-2 2

Sample Output



The line y=\frac{4}{6}x+\frac{8}{6} intersects points (1, 2) and (4, 4). The points (4, 4) and (7, 1) are intersected by the line y=-x+8. Thus, there are two possible slopes.


There are no comments at the moment.