let cross ox oy ax ay bx by =
  (ax - ox) * (by - oy) - (ay - oy) * (bx - ox)

let hull_size pts =
  let n = List.length pts in
  if n < 3 then n
  else begin
    let sorted = List.sort (fun (a, b) (c, d) ->
      if a <> c then compare a c else compare b d) pts in
    let arr = Array.of_list sorted in
    let h = Array.make (2 * n) (0, 0) in
    let k = ref 0 in
    for i = 0 to n - 1 do
      let (xi, yi) = arr.(i) in
      let cont = ref true in
      while !cont && !k >= 2 do
        let (ox, oy) = h.(!k - 2) in
        let (ax, ay) = h.(!k - 1) in
        if cross ox oy ax ay xi yi <= 0 then k := !k - 1
        else cont := false
      done;
      h.(!k) <- (xi, yi);
      k := !k + 1
    done;
    let lo = !k + 1 in
    for i = n - 2 downto 0 do
      let (xi, yi) = arr.(i) in
      let cont = ref true in
      while !cont && !k >= lo do
        let (ox, oy) = h.(!k - 2) in
        let (ax, ay) = h.(!k - 1) in
        if cross ox oy ax ay xi yi <= 0 then k := !k - 1
        else cont := false
      done;
      h.(!k) <- (xi, yi);
      k := !k + 1
    done;
    !k - 1
  end

;;

hull_size [(0, 0); (1, 1); (2, 0); (2, 2); (0, 2); (1, 0); (3, 3); (5, 1)]
