12307 - Smallest Enclosing Rectangle

All about problems in Volume 123. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
shibly
New poster
Posts: 5
Joined: Wed Sep 22, 2010 7:32 am

12307 - Smallest Enclosing Rectangle

Post by shibly » Mon Oct 03, 2011 6:42 pm

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.

rujialiu
New poster
Posts: 37
Joined: Mon Mar 05, 2007 2:42 am

Re: 12307 - Smallest Enclosing Rectangle

Post by rujialiu » Mon Oct 31, 2011 11:24 am

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

caioaao
New poster
Posts: 1
Joined: Sat May 10, 2014 6:29 am

Re: 12307 - Smallest Enclosing Rectangle

Post by caioaao » Sat May 10, 2014 6:31 am

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12307 - Smallest Enclosing Rectangle

Post by brianfry713 » Mon May 12, 2014 11:25 pm

Check input and AC output for thousands of problems on uDebug!

simonpegg
New poster
Posts: 1
Joined: Sat May 31, 2014 2:56 am

Re: 12307 - Smallest Enclosing Rectangle

Post by simonpegg » Sat May 31, 2014 2:59 am

hmm i'm not to sure about this one

Post Reply

Return to “Volume 123 (12300-12399)”