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

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

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
  • Проголосовать: не нравится

»
8 лет назад, скрыть # |
 
Проголосовать: нравится +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).

→ Ответить