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

UVA: 12307 - Smallest Enclosing Rectangle
Автор shibly, 13 лет назад, По-английски

Smallest Enclosing Rectangle of some points id 2D plane where the number of points is 100000. The points will not be collinear. I need some idea to solve the problem.

Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=278&problem=3729&mosmsg=Submission+received+with+ID+9328461

Thanks.

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

13 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

I suppose that smallest rectangle would necessary have at least one of sides which contains at least two of points on it (and other sides would have at least one point each).

So you may start with searching for convex hull for this set. One of its bordering line would be the same as one of the required rectangle's side. You are just to check each of the hull borders, build minimal rectangle upon it and select minimum of all these rectangles. Though I suppose that you may need to optimize series rectangle building so that if convex hull have M points, you build M rectangles in O(M), not O(N*M).

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

Thanks a lot RodionGork. I am trying.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I am getting WA. Can you give me more hints?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    I fear that it is impossible to give any hint without knowing what are you doing to get WA. There could be few possibilities:
    - proposed algorithm is wrong;
    - your implementation is not correct.

    Does it work correctly for proposed testcase?
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
My code works correctly for proposed test cases. Can you send me your code? My mail address is:  [email protected]
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    I fear I can't. I never saw this problem before you asked and I never tried to implement it. Sorry - my idea is based only on some related problems which I tried to solve in past times. :D
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks again for trying to help me. I saw the same problem before and tried. There may be a way called Rotating calipers . But I have no idea abut that. 

Can any one give me some new idea to solve this problem?

→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

You can do the following:


-Build a convex hull

-For each straight line segment(points  [i, i+1]) in the convex hull find the furthest point from it (let it be j)(furthest from the straight line, not just the segment). You can do it in O(N) with two iterators.

So now you know for each line segment the width of the rectangle, if one of its sides passes through that segment (width = distance from the straight line passing through [i, i+1] to point j).

Next step is finding the optimal length for each of the segments. Since you know the furthest point j, you can divide the convex hull into two parts ([i+1..j], [i..j]) and do a ternary search (UPD: or even repeat the same approach with two iterators as before) on each to find the furthest point of the convex hull from a straight line that is perpendicular to [i, i+1] and passes through the point j. Then the length is the distance from the furthest of [i+1..j] to the furthest of [i..j].

Now you know both optimal length and width, so you can easily find the minimum area. (Hope the solution is right)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Thanks a lot ACube. I will try using your logic.
→ Ответить