Problem 102 - 三角形の内外判定

はじめての非離散系?


Problem 102 - PukiWiki

2次元にマッピングされた三角形が原点を含むかどうか判定する。


原点,点A,点Bのz方向の外積を取ってみて、全て同じ方向を向いてたら、含んでる。


ベクトルの話なんか忘れちゃったよ。必死でフルスクラッチ本読んだ。

(define (make-triangle l)
  (if (null? l)
      '()
      (cons (cons (car l) (cadr l))
            (make-triangle (cddr l)))))

(define (inner? l)
  (let* ((check (lambda (p1 p2)
                 (positive? (- (* (- (car p1)) (- (cdr p1) (cdr p2)))
                               (* (- (cdr p1)) (- (car p1) (car p2)))))))
         (rot-apply (lambda (n) (check (list-ref l n) (list-ref l (modulo (+ n 1) 3)))))
         (sign (rot-apply 0)))
    (and (eq? sign (rot-apply 1))
         (eq? sign (rot-apply 2)))))

(length (filter inner? (map make-triangle *data102*))) ; 228

参考