Ineffective guards

2

49 votes
Easy, Geometry, Line Sweep Technique, Math, Sorting
Problem

You are the owner of a jewelry store. It has a very strange structure. There are N points where guards are situated. The ith guard is situated at the point (xi , yi). There are also M pieces of jewelry. The ith jewelry is situated at the point (xi , yi).

If yiyj∣≤xjxi, then the ith guard can see the jth point. 

It is guaranteed that every jewelry is visible by at least one guard and there is at most one object (jewelry or guard) at one point. 

If a guard is removed from his or her place and every jewelry is still visible to at least one guard, then the removed guard is considered to be ineffective. Your task is to calculate the number of ineffective guards.

Input format

  • First line: Two numbers N and M that represents the number of guards and jewelry respectively
  • Next N lines: Two integers xi and yi that represent the coordinates of the ith guard
  • Next M lines: Two integers xi and yi that represents the coordinates of the ith jewelry

Output format

Print exactly one integer that represents the number of ineffective guards.

Constraints

1N2105,1M2105

108xi,yi108

108xi,yi108

Sample Input
3 3
-1 -1
-3 -1
-100 -150
0 0
-2 0
-94 -145
Sample Output
1
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

The second guard is almost useless because he sees only second jewellery. The first guard sees first and second jewellery, so the second guard can be easily removed.

Editor Image

?