; Question 1
; This solution uses the Euclidean distance metric. The Manhattan (sum of the
; two side lengths) distance metric is also acceptable. The maximum length
; metric is also accceptable, although it is an unusual choice.

; Many students observed that it isn't necessary to take the square root when
; performing the Euclidean distance metric. This is acceptable because we are
; comparing distances and aren't interested in the actual values.

; First a few functions to make things a little more readable. Most of them are
; from part II of the homework.

(define (square x) (* x x))

(define (mp x y) (list x y))

(define x-point car)

(define y-point cadr)

(define (distance p)
  (sqrt (+ (square (x-point p)) (square (y-point p)))))

; Now the closer-than? function.

(define (closer-than? p1 p2)
  (if (and (= (length p1) 2) (= (length p2) 2))
      (< (distance p1) (distance p2))
      (error "error in input")
  )
)


; Question 2
; The relative order of points in the original list should be maintained but
; it's not essential if we are using partition-points in the quicksort function.

(define (partition-points x lst)
  (if (null? lst) (list '() '())

    (let ((head (car lst))
          (partitioned-rest (partition-points x (cdr lst))))

         (if (closer-than? head x)
             (list (cons head (car partitioned-rest)) (cadr partitioned-rest))

             (list (car partitioned-rest) (cons head (cadr partitioned-rest)))
         )
    )
  )
)

; Tail recursive version. Note that the helper function is defined within
; the main function, so 'x' can be referred to without passing it into the
; helper function itself.

; This version ends up with the order of the points in each of the lists
; returned being reversed, which doesn't actually matter for quicksort.

(define (cons-first-list x lst) (list (cons x (car lst)) (cadr lst)))

(define (cons-second-list x lst) (list (car lst) (cons x (cadr lst))))

(define (partition-points-tail-recursive x lst)
  (define (partition-points-helper return-list lst)
    (if (null? lst) return-list

        (let ((head (car lst))
              (tail (cdr lst)))

             (if (closer-than? head x)
                 (partition-points-helper
                   (cons-first-list head return-list) tail)

                 (partition-points-helper
                   (cons-second-list head return-list) tail)
             )
        )
    )
  )

  (partition-points-helper '(() ()) lst)
)


; Question 3
; The 'pivot' element is always the first element of the list. This gives
; abysmal performance if the list is sorted ascending or descending. However
; this question isn't about performance.

(define (quicksort-points lst)
  (if (null? lst) '()

      (let ((pivot (car lst)))

           (let ((partitioned (partition-points pivot (cdr lst))))

                (let ((sorted-bottom (quicksort-points (car partitioned)))
                      (sorted-top (quicksort-points (cadr partitioned))))

                     (append sorted-bottom (list pivot) sorted-top)
                )
           )
      )
  )
)