We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Project Euler #102: Triangle containment
Project Euler #102: Triangle containment
Sort by
recency
|
26 Discussions
|
Please Login in order to post a comment
Python
Area of triangle = sum of areas of triangles formed by the point
I don't know why everybody here makes this problem too complicated by using Interior Triangle (Convex Hull) or Barycentric Coordinate. Just think about highschool math.
Hint: Calculate the area S of ABC, OAB, OAC and OBC. If O is inside ABC, then S_ABC = S_OAB + S_OAC + S_OBC.
Trick: To avoid numerical errors, use
abs(S_ABC - S_OAB - S_OAC - S_OBC) < 1e-9
instead ofS_ABC == S_OAB + S_OAC + S_OBC
If (0 ,0) is in the perimeter, the problem statement does not make clear if it should be considered an interior point. Neither did the original project euler statement, but there didn't affect the outcome since there were no triangle with sides intersecting (0, 0).
But here thet distinction matters, particularly in Test #1. And the answer is YES, if (0, 0) is in one side of the triangle, then it is considered interior.
Triangle Interior (WolframMathWorld)