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 a and b, which area is equal to S. There will be d such rectangles, where d is amount of divisors of S. 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 sides a and b and 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 109 then our area S has to be multiplied by 1018, so our new area is equal to S' = S * 1018. Moreover sides of our rectangle will be multiplied by 109, 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 and S around 109 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 109, 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"
time per query.
This can be solved in
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(n3)
You can assume that one point is in the upper right corner. we can't