922 - Rectangle by the Ocean

[ashugoyal]

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

[taufique]

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

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.

[helpkoren]

could some1 give me some test cases ??

[Jehad Uddin]

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.