Solution for a classic algo problem

Carrotland.hs

#!./stack
-- stack --resolver lts-2.14 --install-ghc runghc --package hspec --package QuickCheck
module Carrotland where

import Data.List (sort, find, partition)
import Data.Maybe (fromMaybe)

type Point = (Integer, Integer)

-- projection of a segment on X and Y axes, respectively
project :: Point -> Point -> (Integer, Integer)
project (x1, y1) (x2, y2) = ((abs $ x2 - x1), (abs $ y2 - y1))

-- number of grid points sitting on a segment
lineI :: Point -> Point -> Integer
lineI a b =
    uncurry gcd (project a b) - 1
  where
    gcd a 0 = a
    gcd a b = gcd b (a `mod` b)

-- number of grid points inside a rectangle
rectI :: Point -> Point -> Integer
rectI a b =
    (w - 1) * (h - 1)
  where
    (w, h) = project a b

-- calculate whether the points A and B are on opposite sides of the Q-W line
onOppositeSides :: Point -> Point -> Point -> Point -> Bool
onOppositeSides (qx, qy) (wx, wy) (ax, ay) (bx, by) =
    s1 * s2 < 0
  where
    -- squared area of the Q-W-A triangle
    s1 = (qy - wy) * (ax - qx) + (wx - qx) * (ay - qy)
    -- squared area of Q-W-B triangle
    s2 = (qy - wy) * (bx - qx) + (wx - qx) * (by - qy)

-- number of grid points inside a right triangle
rightTriangleI :: Point -> Point -> Integer
rightTriangleI a b =
    (rectI a b - hI) `div` 2 + hI
  where
    -- number of grid points on the triangle's hypotenuse
    hI = lineI a b

carrots :: Point -> Point -> Point -> Integer
carrots a b c =
    let ps = [a, b, c]
        xs = map fst ps
        ys = map snd ps

        -- bounds of the outer rectangle
        (minX, minY) = (minimum xs, minimum ys)
        (maxX, maxY) = (maximum xs, maximum ys)

        -- grid points in the outer rectangle; total grid points
        totalI = rectI (minX, minY) (maxX, maxY)

        -- compensation values, general case
        c1 = rightTriangleI a b
        c2 = rightTriangleI a c
        c3 = rightTriangleI b c

        -- acute angle case; in this case we need to also compensate for the inner rectangle,
        -- that lies on the acute angle point and one of the outer rectangle points
        c4 = fromMaybe 0 $ do
            -- acute angle point: the only one that will be strictly inside the outer rectangle;
            -- there might be none.
            pa <- find (\(x, y) -> x > minX && x < maxX && y > minY && y < maxY) ps

            -- all four points of the outer rectangle
            let rps = [(x, y) | x <- [minX, maxX], y <- [minY, maxY]]

            -- split all outer rectangle points into:
            -- * "shared" points – those, that are also the triangle's points
            -- * "strictly" rectangle points – those, that don't belong to the triangle
            let ([sp1, sp2], srps) = partition (`elem` ps) rps

            -- opposite point of the inner rectangle
            let po = head $ filter (not . onOppositeSides sp1 sp2 pa) srps
            -- width and height of the inner rectangle
            let (irw, irh) = project pa po

            return $ rectI pa po + irw + irh - 1

    in
        totalI - c1 - c2 - c3 - c4