Блог пользователя learner_321

How to solve this problem ?
Автор learner_321, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить