How do I find index of the smallest enclosing rectangle?

Revision en2, by NeverN, 2018-11-05 09:24:59

Given a list containing N (1 <= N <= 10 ^ 5) rectangles and Q (1 <= Q <= 10 ^ 5) queries. The i-th query will give us a point (u, v). I need to print the index of the smallest rectangle in the list that encloses that point.

  • A rectangle is defined as two points (x1, y1) at the bottom left and (x2, y2) at the top right.
  • x1, y1, x2, y2 are odd numbers.
  • There are no two rectangles intersect with each other
  • u, v are even numbers
  • All coordinates in the input are integers from 1 to 5000, inclusive.

If the statement isn't clear enough, please tell me.

Tags algorithm

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English NeverN 2018-11-05 09:26:06 3 Tiny change: 'will give us a point (' -> 'will give a point ('
en2 English NeverN 2018-11-05 09:24:59 56 Tiny change: 'inclusive.' -> 'inclusive.\n\nIf the statement isn't clear enough, please tell me.' (published)
en1 English NeverN 2018-11-05 09:22:38 589 Initial revision (saved to drafts)