922 - Rectangle by the Ocean

All about problems in Volume 9. 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
New poster
Posts: 1
Joined: Sun Feb 17, 2008 10:18 pm

922 - Rectangle by the Ocean

Post by ashugoyal » Sun Feb 17, 2008 10:32 pm

can anybody please help me to solve problem 922 (rectangle by the ocean).

New poster
Posts: 3
Joined: Fri Nov 05, 2010 10:19 am

Re: 922 - Rectangle by the Ocean

Post by taufique » Tue Nov 16, 2010 7:12 pm

@ashugoyal::: It's about 3 years since you posted :( . I think you dont need this help anymore. :) I just solved the problem right now. But I m posting it in case if
anyone need it(hopefully not :wink: ).

1. At first you have to find the smallest grid to have the map. So certainly you have to determine the highest x, lowest x, highest y,lowest y value of the map.
2. Then you have to create each possible rectangle within that smallest grid through 4 nested loops.(I solved this in this way(O(n^5)). There may be other efficient algorithms)
3. Now in each iteration you have to check that if the area of current rectangle is closest to the map than result.
4. If (3) true then check if at least three points of current rectangle lies on the map.
5. If (4) is true save the current rectangle to the result.

do this thing a little bit intelligent way to get automatically the lexicographically desired result.

New poster
Posts: 1
Joined: Sun Nov 21, 2010 3:46 pm

Re: 922 - Rectangle by the Ocean

Post by helpkoren » Sun Nov 21, 2010 3:49 pm

could some1 give me some test cases ??

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 922 - Rectangle by the Ocean

Post by Jehad Uddin » Fri Dec 31, 2010 11:44 am

O(n^2 log n) is enough for the problem.Take two point and find the other two . Then check two point from the map in log n.

Post Reply

Return to “Volume 9 (900-999)”