Si_jo's blog

[Doubt] Count maximum no. of given points lying inside a rectangle of given size and orientation.
By Si_jo, history, 12 months ago, In English

You are given n points in the x-y plane and a rectangle of given height and width whose sides are aligned with the coordinate axes. You need to tell if you are allowed to translate the rectangle parallel to the axes what is the maximum no of points that can lie inside the rectangle at any point in time.

Yesterday, I quickly realized that the ABC's problem F was essentially this but could not find an optimal solution.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem link doesn't work

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

I think we can use segment tree with Lazy Propagation. Here's how I m thinking. I will iterate along the x-axis,

For any particular window of width w and left endpoint p along x-axis,to get all the points for the next window, i will just remove the points with x-coordinate = p and will add points with x-coordinate = p+w+1.

Now for any new point suppose (x,y) added, i will range update in my segtree [y-h,y] by +1 and for any old point removed suppose (x1,y1), I will range update in my segtree [y1-h,y1] by -1 where h was the height of rectangle.

Now after updation I just want the maximum element.

→ Reply