(* Origami
   Autor : Michał Kardaś
   Reviewer : ?
*)

type point = float * float

type kartka = point -> int

let eps = 1e-9

let meps = -1e-9

(* iloczyn skalarny wektora <ab> i <ac> *)
let skal (ax ,ay) (bx ,by) (cx ,cy) =
  (cx -. ax) *. (bx -. ax) +. (cy -. ay) *. (by -. ay)

(* zakłada, że a!=b
   punkt rzutowania punktu c na prostę wyznaczoną przez punkty a i b *)
let punkt_rzutowania a b c =
  let (ax ,ay) = a and
  (bx ,by) = b  in
  (* ze wzorku wynika, że f jest stosunkiem |ax| do |ac| gdzie
     x jest rzutem punktu c na prostą wyznaczoną przez punkty a b *)
  let f = skal a b c /. skal a b b
  in (ax +. f *. (bx -. ax), ay +. f *. (by -. ay))

(* iloczny wektorowy wektora <ab> i <ac>
   dodatni jeżeli c lezy po lewej stronie idąc od a do b *)
let det (ax ,ay) (bx ,by) (cx ,cy) =
  (bx -. ax) *. (cy -. ay) -. (by -. ay) *. (cx -. ax)

let sgn x =
  if x < meps then -1
  else if x > eps then 1 else 0

(* po ktorej stronie prostej idąc od a do b leży c
   1 - lewej
   0 - leży na prostej
   -1 - prawej *)
let strona a b c =
  sgn (det a b c)

(* zakłada, że a i b są przyczepione do przecięcia osi współrzędnych
   zwraca wektor od konca a do konca b *)
let roznica (ax ,ay) (bx ,by) =
  (ax -. bx ,ay -. by)

(* zakłada, że a i b są przyczepione do przecięcia osi współrzędnych
   zwraca sumę wektorów *)
let suma (ax ,ay) (bx ,by) =
  (bx +. ax ,ay +. by)

(* odbicie punktu c względem prostej wyznaczonej przez punkty a i b *)
let odbicie a b c =
  let rzut = punkt_rzutowania a b c in
    suma rzut (roznica rzut c)

(* kwadrat odległości punktów a i b *)
let odl (ax ,ay) (bx ,by) =
  (ax -. bx) *. (ax -. bx) +. (ay -. by) *. (ay -. by)

let prostokat (ax ,ay) (bx ,by) =
  fun (cx ,cy) -> if (cx -. bx) < eps && (ax -. cx) < eps &&
                     (cy -. by) < eps && (ay -. cy) < eps
    then 1 else 0

(* jeżeli kwadrat odległości środka i punktu a jest mniejszy niż
   kwadrat promienia + eps to a należy do kółka *)
let kolko a r =
  fun c -> if odl a c -. (r *. r) < eps then 1 else 0

let zloz a b kartka =
  fun c -> let po_ktorej = strona a b c in
      (* jezeli po_ktorej = 1 to c leży na lewo od prostej wyznaczonej
         przez punkty a i b więc istnieje niezerowa szansa na to, że
         jakiś punkt z kartki po prawej stronie na niego przeszedł, więc
         dla odbitego punktu jak i punktu c zliczamy wystąpienia w
         poprzednich złożeniach kartki *)
      if po_ktorej = 1
      then kartka c + kartka (odbicie a b c)
      (* punkt c leży na prostej, więc nie zanika ani nie rozbija się *)
      else if po_ktorej = 0
      then kartka c
      (* leży po prawej stronie złożenia, więc pomijamy *)
      else 0

(* składanie funkcji zloz w sposob podany w treści *)
let skladaj l k =
  List.fold_left (fun acc (x ,y) -> zloz x y acc) k l