LashaBukhnikashvili's blog

By LashaBukhnikashvili, history, 5 years ago, In English

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,

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Do sides lengths can only be integers?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    not neccessary :\

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But coordinates are always integers?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like 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

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    "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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)