All Tracks Math Geometry Line Sweep Technique Problem

Ineffective guards
Tag(s):

Easy-Medium, Geometry, Line Sweep Technique, Mathematics, Sorting

Problem
Editorial
Analytics

You are the owner of a jewelry store. It has a very strange structure. There are \(N\) points where guards are situated. The \(i^{th}\) guard is situated at the point (\(x_i\) , \(y_i\)). There are also \(M\) pieces of jewelry. The \(i^{th}\) jewelry is situated at the point (\(x^\prime_i\) , \(y^\prime_i\)).

If \(\mid y_i - y^\prime_j\mid \le x^\prime_j - x_i\), then the \(i^{th}\) guard can see the \(j^{th}\) 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 \(x_i\) and \(y_i\) that represent the coordinates of the \(i^{th}\) guard
  • Next \(M\) lines: Two integers \(x^\prime_i\) and \(y^\prime_i\) that represents the coordinates of the \(i^{th}\) jewelry

Output format

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

Constraints

\(1 \le N \le 2 \cdot 10^{5} , 1 \le M \le 2 \cdot 10^{5}\)

\(−10^{8} \le x_i,y_i \le 10^{8}\)

\(−10^{8} \le x^\prime_i,y^\prime_i \le 10^{8}\)

SAMPLE INPUT
3 3
-1 -1
-3 -1
-100 -150
0 0
-2 0
-94 -145
SAMPLE OUTPUT
1
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.

Time Limit: 2,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

May Circuits '19

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?