HackerRank.com - Functional Programming - Haskell - Concave Polygon

README.md

Concave Polygon

You are given the cartesian coordinates of a set of points in a 2D plane (in no particular order). Each of these points is a corner point of some Polygon, P, which is not self-intersecting in nature. Can you determine whether or not is a concave polygon?

Input Format

The first line contains an integer, N, denoting the number of points. The N subsequent lines each contain 2 space-separated integers denoting the respective x and y coordinates of a point.

Constraints

• 3 <= N <= 1000
• 0 <= x, y <= 1000

Output Format

Print YES if P is a concave polygon; otherwise, print NO.

Sample Input

4
0 0
0 1  
1 1  
1 0

Sample Output

NO

Explanation

The given polygon is a square, and each of its 4 internal angles are 90° . As none of these are over 180°, the polygon is not concave and we print NO.

Scoring

The percentage score awarded for your submission will be:

    100 - 2*(percentage of tests which you solve incorrectly)  

If this value is negative, the percentage score for your submission will be 0.

So if you get half or more of the tests incorrect, your score will be a zero.

a_concave_polygon.hs

import           Data.List
import           Debug.Trace


data Node = Node Int Int
    deriving (Show, Eq)

rad2deg a = a * (180.0 / pi)

sortNodePair (Node ax ay) (Node bx by)
    | ax > bx = GT
    | ax < bx = LT
    | ax == bx = compare ay by

sortNodes n = sortBy sortNodePair n

segLen (Node ax ay) (Node bx by) = sqrt $ xdsq + ydsq
    where
        xdsq = (fromIntegral (bx - ax)) ** 2
        ydsq = (fromIntegral (by - ay)) ** 2


vectorsAngle (Node cx cy) (Node p0x p0y) (Node p1x p1y) = acos((p1c*p1c+p0c*p0c-p0p1*p0p1)/(2*p1c*p0c))
    where
        p0c  = sqrt(((fromIntegral(cx-p0x)) ** 2) + ((fromIntegral(cy-p0y)) ** 2))
        p1c  = sqrt(((fromIntegral(cx-p1x)) ** 2) + ((fromIntegral(cy-p1y)) ** 2))
        p0p1 = sqrt(((fromIntegral(p1x-p0x)) ** 2) + ((fromIntegral(p1y-p0y)) ** 2))

smallestAngle :: [Node] -> [Node] -> Node
smallestAngle [ a, b ] allNodes = node
    where
        angleCurr = vectorsAngle a b
        angles = map angleCurr allNodes
        minAngle = foldr1 min angles
        mbIdx = findIndex (\x -> x == minAngle) angles
        idx = case mbIdx of Just n -> n; Nothing -> 0
        node = allNodes !! idx

giftWrap :: Node -> [Node] -> [Node] -> [Node] -> [Node]
-- giftWrap target poly inits rest | trace ((show poly) ++ "\n" ++ (show inits) ++ "\n" ++ (show rest) ++ "\n\n") False = undefined
-- giftWrap target poly inits rest | trace ((show poly) ++ "\n" ++ "TOTAL POLY POINTS: " ++ (show (length poly)) ++ "\n\n") False = undefined
giftWrap target poly inits rest
    | nextNode == target = reverse poly
    | length poly > ((length (inits ++ rest)) * 2) = nub poly
    | otherwise = giftWrap target wPoly wInits wRest
    where
        nextNode = smallestAngle inits rest
        wPoly = if length poly == 0 then reverse inits else (last inits) : poly
        wInits = (last inits) : nextNode : []
        wRest = (inits ++ rest) \\ wInits

main = do
    raw <- getContents
    let
        lns = tail $ lines raw
        ans = map (\ln -> map (\w -> read w :: Int) (words ln)) lns
        nds = map (\dp -> Node (head dp) (last dp)) ans
        sns = sortNodes nds
        gwr = giftWrap (sns !! 1) [] (take 2 sns) (drop 2 sns)
        res = if (length gwr) == (length sns) then "NO" else "YES"
    putStrLn res

inputConcave.txt

120
452 706
602 472
565 571
1008 668
1038 712
603 536
706 449
606 454
832 1028
817 484
475 892
810 1054
929 976
666 1051
981 620
995 596
982 542
446 687
462 615
716 1051
577 973
693 503
440 761
1020 735
956 503
1051 814
950 983
862 985
634 1046
1012 620
431 749
689 1038
983 587
481 641
1073 835
917 519
565 965
911 477
948 963
826 1056
1010 904
1006 835
732 1027
1018 853
549 512
508 943
854 478
498 861
775 455
459 837
517 970
462 719
915 502
659 501
654 425
482 810
1032 799
480 606
847 985
1059 687
997 874
760 1062
517 951
543 962
744 994
883 494
771 1045
607 1019
741 450
629 1014
429 661
862 506
755 454
652 1033
483 936
976 967
474 737
794 460
990 928
545 591
456 797
480 657
816 430
631 465
896 985
837 476
953 548
882 999
968 575
594 497
463 575
802 1086
1035 644
1067 751
542 533
727 462
950 532
1059 721
1047 765
1036 673
991 913
591 1021
918 992
575 996
704 1059
504 580
523 459
1013 864
1033 623
1058 782
508 905
503 774
507 538
478 905
704 502
491 845
588 1004
986 947
851 1029
784 1059

inputConvex.txt

16
1094 937
713 1157
757 364
981 418
357 717
1129 817
1116 862
555 402
475 1015
420 928
635 1114
410 565
913 1090
1125 693
823 1161
1031 479

outputConcave.txt

YES

outputConvex.txt

NO