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 points where guards are situated. The  guard is situated at the point ( , ). There are also pieces of jewelry. The  jewelry is situated at the point ( , ).

If , then the guard can see the 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 and  that represents the number of guards and jewelry respectively
  • Next lines: Two integers  and  that represent the coordinates of the  guard
  • Next lines: Two integers and  that represents the coordinates of the jewelry

Output format

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

Constraints

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

?