An Animal Contest 4 P3 - Snowy Slopes

View as PDF

Submit solution


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

Author:
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 (xi,yi) where xi represents the horizontal distance from the origin and yi 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 ki and di.

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 kidi.

The gradient of a line joined by two points (x1,y1) and (x2,y2) is equal to y2y1x2x1.

Constraints

2N105

1M20

1xi,yi109

109ki,di109

All xi are distinct.

All yi are distinct.

Neither ki nor di 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 xi and yi, the coordinates of the i-th point.

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

Output Specification

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

Sample Input

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

Sample Output

Copy
2

Explanation

The line y=46x+86 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.


Comments

There are no comments at the moment.