mukesh tiwari mukeshtiwari.iiitm at gmail.com
Wed Aug 17 14:09:52 CEST 2011

```Hello all
I am trying implement this algorithm  [
http://stackoverflow.com/questions/1621364/how-to-find-largest-triangle-in-convex-hull-aside-from-brute-force-search
] in Haskell but i am getting wrong answer for some test cases. A c++
implementation which is accepted for this problem [ http://www.spoj.pl/problems/MTRIAREA
] and i   rewrote  the C++ code in Haskell . Running both programs on
some  random test cases produce different result . For Haskell
implementation , convex hull part is correct . Both codes [ c++ and
looPing :: ( Num a , Ord a , Eq a , Floating a ) => Int -> Int -> Int -
> Int -> a -> Array Int ( Point a ) -> a  and calArea :: ( Num a , Ord
a , Floating a ) => Int -> Int -> Int  -> Int  -> a -> Array Int
( Point a ) -> ( Int , Int , Int , a ) function . Could some one
please tell me what is wrong with these functions. I have posted both
code on ideone . Haskell code [ http://ideone.com/IlwBv ] and accepted
c++ for SPOJ problem [ http://ideone.com/vgNnt ] . For test case
20
886 9383
6915 2777
8335 7793
492 5386
1421 6649
27 2362
59 8690
3926 7763
3426 540
5736 9172
5368 5211
6429 2567
1530 5782
5123 2862
3135 4067
9802 3929
3058 4022
8167 3069
8456 1393
8042 5011
-1
Haskell produced the convex hull [P 27.0 2362.0,P 3426.0 540.0,P
8456.0 1393.0,P 9802.0 3929.0,P 8335.0 7793.0,P 5736.0 9172.0,P 886.0
9383.0,P 59.0 8690.0] and maximum triangle area 31466755.50 while C++
code produced the convex hull
27 2362
3426 540
8456 1393
9802 3929
8335 7793
5736 9172
886 9383
59 8690
and maximum area 33642111.00 . Based on these observation , I think my
convex hull part is correct and I am stuck with looPing and calArea
function . I tried to write Haskell code many ways but no success so
it would be great if some one can tell me what is wrong with these two
functions .

Thank you

```