grahamscan.hs

import Data.List
import Text.Printf

type Point = (Int, Int)

ccw :: Point -> Point -> Point -> Int
ccw p1 p2 p3 = (fst p2 - fst p1) * (snd p3 - snd p1)
               - (snd p2 - snd p1) * (fst p3 - fst p1)


-- function ccw(p1, p2, p3):
--     return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x)

rightTurn :: Point -> Point -> Point -> Bool
rightTurn p1 p2 p3 = ccw p1 p2 p3 < 0

leftTurn :: Point -> Point -> Point -> Bool
leftTurn p1 p2 p3 = ccw p1 p2 p3 > 0

lineDist :: Point -> Point -> Point -> Double
lineDist (x1, y1) (x2, y2) (x0, y0) =
    (fromIntegral $ abs ((y2 - y1) * x0 - (x2 - x1) * y0 + x2 * y1 - y2 * x1))
    / (sqrt $ fromIntegral $ (y2 - y1) ^ 2 + (x2 - x1) ^ 2)

quickHull :: [Point] -> [Point]
quickHull ps =
    let compX = (\x y -> compare (fst x) (fst y))
        minP = minimumBy compX ps
        maxP = maximumBy compX ps
        (ls, rs) = partition (leftTurn minP maxP) $ delete minP $ delete maxP $ ps
        lh = quickHull' minP maxP ls
        rh = quickHull' maxP minP $ filter (leftTurn maxP minP) rs
    in lh ++ rh where
        quickHull' from to [] = [from]
        quickHull' from to ps =
            let thirdPoint = maximumBy (\p1 p2 -> compare (lineDist from to p1)
                                                  (lineDist from to p2)) ps
                ps1 = filter (leftTurn from thirdPoint) ps
                ps2 = filter (leftTurn thirdPoint to) ps
            in quickHull' from thirdPoint ps1 ++ quickHull' thirdPoint to ps2

dist :: Point -> Point -> Double
dist (x1, y1) (x2, y2) =  sqrt $ fromIntegral $ (x2 - x1) ^ 2 + (y2 - y1) ^ 2

perimiter :: [Point] -> Double
perimiter ps = perimiter' (ps ++ [head ps]) 0
perimiter' (p1 : p2 : ps) acc =
    perimiter' (p2 : ps) $ acc + dist p1 p2
perimiter' _ acc = acc


solve :: [(Int, Int)] -> Double
solve points = perimiter $ quickHull points

main :: IO ()
main = do
  n <- readLn :: IO Int
  content <- getContents
  let
    points = map (\[x, y] -> (x, y)). map (map (read::String->Int)). map
             words. lines $ content
    ans = solve points
  printf "%.1f\n" ans