;; Problem 102
;; 12 August 2005

;; Three distinct points are plotted at random on a Cartesian plane, for which -1000 x, y 1000, such that a triangle is formed.

;; Consider the following two triangles:

;; A(-340,495), B(-153,-910), C(835,-947)

;; X(-175,41), Y(-421,-714), Z(574,-645)

;; It can be verified that triangle ABC contains the origin, whereas triangle XYZ does not.

;; Using triangles.txt (right click and 'Save Link/Target As...'), a 27K text file containing the co-ordinates of one thousand "random" triangles, find the number of triangles for which the interior contains the origin.

;; NOTE: The first two examples in the file represent the triangles in the example given above.

(defvar *the-file* "/home/mortis/personal/projects/project-euler/data-files/triangles.txt")

;; (asdf-install:install 'vecto)
(require 'vecto)

;; (asdf-install:install 'cl-utilities)
(require 'cl-utilities)


(defun group-by-2s (things)
  (labels ((grp (acc lst)
	     (cond ((null lst)
		    (reverse acc))
		   ((= 1 (length lst))
		    (reverse (cons (list (first lst)) acc)))
		   (t
		    (grp (cons (list (first lst) (second lst)) acc)
			 (cddr lst))))))
    (grp (list) things)))

(defvar *triangles*
  ;;(setf *triangles*
  (mapcar #'group-by-2s
	  (with-open-file (in *the-file* :direction :input )
	    (loop for line = (read-line in nil nil)
		  while line
		  collect (mapcar #'read-from-string
				  (cl-utilities:split-sequence #\, line))))))

;;(first *triangles*)

(defun graph-translate (pairs)
  (loop for pair in pairs
	collect (loop for coord in pair
		      collect (+ 1000 coord))))

(defun translate-pair (pair)
  (list (+ 1000 (first pair))
	(+ 1000 (second pair))))

;; (translate-pair '(0 0))

;;(graph-translate '((-100 100) (100 100)))
	
;; (first *triangles*) ; '((-340 495) (-153 -910) (835 -947))


;; i think the following test works: if the line from a point through
;; the origin falls between the other two points (or lines), and this
;; proprty is true of all three points, then the origin ins contained
;; within the triangle

(defun slope (p1 p2)
  (let ((x1 (first p1))
	(y1 (second p1))
	(x2 (first p2))
	(y2 (second p2)))
    (/ (- y2 y1)
       (- x2 x1))))

;; (slope '(1 0) '(0 1))

(defun find-line-coeficients (pt1 pt2)
  (let* ((a (- (second pt2) (second pt1)))
	 (b (- (first pt1) (first pt2)))
	 (c (+ (* a (first pt1))
	       (* b (second pt1)))))
    ;(format t "~ax+~ay=~a~&" a b c)
    (list a b c)))

;;(find-line-coeficients '(-340 495) '(-153 -910))
;;(find-line-coeficients '(835 -947) '(-340 495))

;;(first *triangles*)((-340 495) (-153 -910) (835 -947))

;; 'l1:(a b c) l2:(a b c)
(defun find-line-intersect (l1 l2)
  (let ((det (- (* (first l1) (second l2))
		(* (first l2) (second l1)))))
    (cond ((= 0 det)
	   nil)
	  (t
	   (list
	    (/
	     (- (* 1.0 (second l2) (third l1))
		(* (second l1) (third l2)))
	     det)
	    (/
	     (- (* 1.0 (first l1) (third l2))
		(* (first l2) (third l1)))
	     det))))))

; (find-line-intersect '(1 -1 0) '(1 1 0))
; (find-line-intersect '(1 -1 0) '(1 1 1))

(defun plot-triangle (points file-name)
  (let ((width 2000)
	(height 2000))
    (vecto:with-canvas (:width width :height height)

      (vecto:translate 1000 1000)

      (vecto:set-rgb-stroke 0 0 0)
      (vecto:set-line-width 2)

      ;; draw origin lines
      (vecto:move-to 0 1000)
      (vecto:line-to 0 -1000)
      (vecto:move-to 1000 0)
      (vecto:line-to -1000 0)
      (vecto:stroke)
      (vecto:set-font (vecto:get-font "/usr/share/fonts/truetype/freefont/FreeSans.ttf") 40)
      (vecto:draw-centered-string 0 0 "o(0,0)")


      (loop for prev-point = (first (reverse points))
	    then next-point
	    for label in '("c" "a" "b" "c")
	    for next-point in points
	    do
	    (format t "from:~a ~a to:~a~&" label prev-point next-point)
	    (vecto:move-to (first prev-point) (second prev-point))
	    (vecto:set-font (vecto:get-font "/usr/share/fonts/truetype/freefont/FreeSans.ttf") 40)
	    (vecto:draw-centered-string (first prev-point) (second prev-point) (format nil "~a:~a" label prev-point))
	    (vecto:line-to (first next-point) (second next-point)))

      (let* ((pt-a (first points))
	     (pt-b (second points))
	     (pt-c (third points)))
	(format t "ao:~a" (find-line-coeficients pt-a '(0 0)))
	(format t "bc:~a" (find-line-coeficients pt-b pt-c))
	(format t "isect:~a"
		(find-line-intersect (find-line-coeficients pt-a '(0 0))
				     (find-line-coeficients pt-b pt-c))))
      
      (vecto:stroke)

      (vecto:save-png file-name))))

;;(plot-triangle '((10 10) (20 20) (10 20)) "/home/mortis/personal/projects/project-euler/example1.png")
(plot-triangle (first *triangles*) "/home/mortis/personal/projects/project-euler/example1.png")

(defun point-between (a b c)
  (let ((x1 (first a))
	(x2 (first b))
	(x3 (first c))
	(y1 (second a))
	(y2 (second b))
	(y3 (second c)))
    (format t "x1:~a x2:~a x3:~a y1:~a y2:~a y3:~a~&"
	    x1 x2 x3 y1 y2 y3)
    (and (or (<= x1 x2 x3)
	     (>= x1 x2 x3))
	 (or (<= y1 y2 y3)
	     (>= y1 y2 y3)))))

(defun contains-origin (triangle)
  (let* ((a (first triangle))
	 (b (second triangle))
	 (c (third triangle))
	 (ac-isect
	  (find-line-intersect 
	   (find-line-coeficients a c)
	   (find-line-coeficients b '(0 0))))
	 (ab-isect
	  (find-line-intersect
	   (find-line-coeficients a b)
	   (find-line-coeficients c '(0 0))))
	 (bc-isect
	  (find-line-intersect
	   (find-line-coeficients b c)
	   (find-line-coeficients a '(0 0)))))
    (format t "A:~a~&" a)
    (format t "B:~a~&" b)
    (format t "C:~a~&" c)
    (format t "AC-ISECT:~a~&" ac-isect)
    (format t "AB-ISECT:~a~&" ab-isect)
    (format t "BC-ISECT:~a~&" bc-isect)

    (and
     (point-between a ac-isect c)
     (point-between a ab-isect b)
     (point-between b bc-isect c))))

(contains-origin (first *triangles*))
;(let ((triangle '((100 100) (400 200) (100 200))))
(let ((triangle (first *triangles*)))
  (if nil (plot-triangle triangle "/home/mortis/personal/projects/project-euler/example2.png"))
  (contains-origin triangle))

(time
 (let ((res 0))
   (loop for triangle in *triangles*
	 do
	 (when (contains-origin triangle)
	   (format t "found:~a~&" triangle)
	   (incf res)))
   (format t "total:~a~&" res)
   res))