Please read the new rule regarding the restriction on the use of AI tools. ×

Points inside Rectangles

Revision en1, by OmarKimo, 2021-09-06 13:34:20

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, <= 10^6) and n&m <= 10^6. 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)