Points inside Rectangles

Revision en2, by OmarKimo, 2021-09-06 13:38:51

Let's say that we have n Rectangles with known coordinates and m Points with known coordinates.
How to count the number of points that lie inside each Rectangle given that the coordinates are integers (>= 0, <= 106) and n & m <= 106.
Surely, the complexity of O(n*m) is not desirable!
I think of Segment Tree but don't know how and if it's better or not!

May you help me, please?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English OmarKimo 2021-09-06 13:38:51 58 Tiny change: 'rdinates.</br>\nHow t' -> 'rdinates.<br>\nHow t'
en1 English OmarKimo 2021-09-06 13:34:20 409 Initial revision (published)