Here is given n(n=1000) points on the plane, each described by (x,y). need to place a rectangle of area S on the plane. Sides of a rectangle should be paralel to X and Y axis. required to find maximal number of points that can be contained by a single rectangle.

I need to find maximum O(N^2 * K) solution to solve problem, where K is answer (maximum amount of points among all rectangle with area S),

thanks in advance,

Do sides lengths can only be integers?

not neccessary :\

But coordinates are always integers?

Ok,multiply them by 10^9 ,they are now integers,what then :) ?

First let me show you a solution which works for integer points and in the case when sides have to be integers too.

Let's find all rectangles of sides

aandb, which area is equal toS. There will bedsuch rectangles, wheredis amount of divisors ofS. Now consider each rectangle exclusively. While doing that, for each point let's find area in which the top-left corner of rectangle can be placed so it will contain this point. This area will be a rectangle of sidesaandband bottom-right corner in that point. Now all we need to do is find maximum set of rectangle with common part. It can be done in by using segment tree and sweeping technique. So whole complexity is or .We can't use such an approach when it's not provided that coordinates as well as sides of rectangle gonna be integers. But do we really can't use it without such a requirements?

If we change cooridnates to integers by multiplying everything by 10

^{9}then our areaShas to be multiplied by 10^{18}, so our new area is equal toS' =S* 10^{18}. Moreover sides of our rectangle will be multiplied by 10^{9}, so now they are integeres too! Now when everything is integer we can use solution above, but it's complexity gonna be worse cause , so in case of high coordinate precision it won't pass but with precision around 10^{ - 3}andSaround 10^{9}it should be fine.Correct last part if I'm wrong, because I'm not 100% sure about it.

no It's not correct points,to find divisions of S and set them as the rectangle sides,because sides may be any real number

After multiplying by 10

^{9}, real numbers which precission doesn't exceed 10^{ - 9}gonna become integers and finding divisors will work for them if both side precission doesn't exceed 10^{ - 9}if it does then it won't work.You can iterate through all pairs of points and each time find number points inside this rectangle in average. This can be done with 2d tree range-search or 2d segment tree.So u get

how you are going to fix a whole rectangle with only two points? (these points are not neccessary vertices of rectangle)

Suppose answer is some rectangle. And if we try to make this rectangle smaller by decreasing up-right corner u get stuck to some point in the set. In the same manner u get second points. And when we iterate through points we try see them in this positions.

we will have reached the points,which will be located on side of rectangle,not on the vertices location,and with just 2 points on the different side of rectangle we can fix it

Yes, you are right! I will try to fix this.

"find number points inside this rectangle"

This can be solved in time per query.

P.S. If the sides of the rectangle are integers you should iterate over divisors of

S.You can assume that one point is in the upper right corner. Iterate over all points and fix the upper right corner. For each of the other points find the interval of rectangle heights such that the point is inside the rectangle (if not possible: simply skip the point):

O(n). Find the point which is covered by most intervals: . Take the maximum of all outer iterations.Total complexity: . Not exactly what you were looking for, but at least much better than

O(n^{3})You can assume that one point is in the upper right corner.we can't