From 83ca7628fbba1b99cfd60bf6e40b5e76d7a0d5f1 Mon Sep 17 00:00:00 2001
From: Reiner Herrmann <reiner@reiner-h.de>
Date: Wed, 30 Nov 2011 23:29:14 +0100
Subject: solve 102 via Cramer's rule to get rid of workaround

---
 src/projecteuler/102.py | 16 +++++++++++-----
 1 file changed, 11 insertions(+), 5 deletions(-)

diff --git a/src/projecteuler/102.py b/src/projecteuler/102.py
index e506516..a2108f6 100644
--- a/src/projecteuler/102.py
+++ b/src/projecteuler/102.py
@@ -1,16 +1,22 @@
 
+# check if r*(AC) + s*(AB) == P
+
 def point_in_triangle((x_a, y_a), (x_b, y_b), (x_c, y_c), (x_p, y_p)):
     t = x_c - x_a
     u = x_b - x_a
     v = y_c - y_a
     w = y_b - y_a
 
-    # workaround for horizontal lines
-    if t == 0:
-	t = 0.00000000000000001
+    # Cramer's rule
+    detA = t*w - u*v
+    detR = x_p*w - u*y_p
+    detS = t*y_p - x_p*v
+
+    if detA == 0:
+	print "Not solvable"
 
-    s = (y_p - (x_p*v/float(t))) / (float(w) - u*v/float(t))
-    r = (x_p - u*s) / float(t)
+    r = detR / float(detA)
+    s = detS / float(detA)
 
     return 0 <= r <= 1 and 0 <= s <= 1 and r + s < 1
 
-- 
cgit v1.2.3