Project Euler #102: Triangle containment

Sort by

recency

|

26 Discussions

|

  • + 0 comments

    Python

    def calculate_triangle_area(x1, y1, x2, y2, x3, y3):
        area = 0.5 * abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))
        return area
    
    
    ret = 0
    for _ in range(int(input())):
        x1, y1, x2, y2, x3, y3 = map(int, input().split())
        area = calculate_triangle_area(x1, y1, x2, y2, x3, y3)
        area1 = calculate_triangle_area(0, 0, x2, y2, x3, y3)
        area2 = calculate_triangle_area(x1, y1, 0, 0, x3, y3)
        area3 = calculate_triangle_area(x1, y1, x2, y2, 0, 0)
        
        if area == area1 + area2 + area3:
            ret += 1
            
    print(ret)
    
  • + 0 comments

    Area of triangle = sum of areas of triangles formed by the point

  • + 1 comment

    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 of S_ABC == S_OAB + S_OAC + S_OBC

  • + 0 comments

    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.

  • + 0 comments

    Triangle Interior (WolframMathWorld)