Usu's blog

By Usu, history, 5 years ago, In English

Hey! I discovered a type of problems where we have for example n points and we want to discover the convex hull (the border) using some of those points, but after that calculate the area of the smallest rectangle in which that convex hull can lie inside. I saw that we can rotate the convex hull with some degrees, but I didn't understand it very well. Can anybody give me more details about how to rotate a convex hull with sin and cos, some links eventually. Thanks!

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

5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Maybe this should work: For each edge of the convex hull, rotate it so that the edge becomes parallel to x-axis, then draw rectangle with leftmost, rightmost, topmost point and the edge. For the rotation see this:

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

Hi. Could you please post some problems related to this from online judges?