learner_321's blog

How to solve this problem ?
By learner_321, history, 7 years ago, In English

You are given n poins in 2 dimesnsion.you need to find out minimum area of rectangle with atleast k points ?

1<=n<=200 0<=x<=40000 0<=y<=40000 1<=k<=n

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

In the optimal rectangle, there will always be points in its borders, otherwise we would be able to shrink them. With this in mind, all you have to do is: fix a pair of points to settle the rectangle's rows and, then, use two pointers to settle the columns, taking in account the condition of at least k points. This should work in O(n3).

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

    can you please explain how to do this ?

    use two pointers to settle the columns, taking in account the condition of at least k points

    → Reply