Page 1 of 1

12307 - Smallest Enclosing Rectangle

Posted: Mon Oct 03, 2011 6:42 pm
by shibly
I need some idea to solve this problem. I code the problem and got WA.

My logic is given below:

1.At first find the convex hull.
2.There is at least one edge of rectangle which will overlap with one edge of the convex hull.

Am I right ? If yes then I need some critical input output.

Thanks.

Re: 12307 - Smallest Enclosing Rectangle

Posted: Mon Oct 31, 2011 11:24 am
by rujialiu
The basic idea is correct. Attention to colinear points especially when you're calculating convex hull by granham's original algorithm, not andrew's variation (this one is preferred). You can send me an email with your code and I'll test it with judge data.

Re: 12307 - Smallest Enclosing Rectangle

Posted: Sat May 10, 2014 6:31 am
by caioaao
Hello, I know this is a really old topic, but I need help on this one. I'm using four rotating calipers to do the job, but I keep getting WA. Can someone provide me some tricky cases or take a look at my code? idk if I can post it here thou

Re: 12307 - Smallest Enclosing Rectangle

Posted: Mon May 12, 2014 11:25 pm
by brianfry713

Re: 12307 - Smallest Enclosing Rectangle

Posted: Sat May 31, 2014 2:59 am
by simonpegg
hmm i'm not to sure about this one