[Doubt] Count maximum no. of given points lying inside a rectangle of given size and orientation.

Revision en1, by Si_jo, 2023-11-05 07:25:20

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.

Tags computational geometry, doubt


  Rev. Lang. By When Δ Comment
en1 English Si_jo 2023-11-05 07:25:20 526 Initial revision (published)