Lisp Number Of Disc Intersections
(defun number-of-disc-intersections (a)
(let* ((vec (coerce a 'vector))
(c (length vec))
(start (make-array c :initial-element 0))
(end (make-array c :initial-element 0))
(sum 0)
(active 0))
(loop for k from 0 below c
for v = (aref vec k)
do (let ((key1 (if (< k v) 0 (- k v)))
(key2 (if (>= (+ k v) c) (1- c) (+ k v))))
(incf (aref start key1))
(incf (aref end key2))))
(loop for k from 0 below c
do (progn
(incf sum (+ (* active (aref start k))
(/ (* (aref start k) (1- (aref start k))) 2)))
(incf active (- (aref start k) (aref end k)))
(when (> sum 10000000)
(return-from number-of-disc-intersections -1))))
sum))
This sorts disc start and end points and counts active overlaps without comparing every pair directly.