0012: A Point in a Triangle

三角形と点

解き方

外積を利用する。３つのベクトルが全て同じ方向を向いているとき、点Pは三角形の内側にある。

コード(python)

while True:
    try:
        x1, y1, x2, y2, x3, y3, xp, yp = map(float, input().split())
    except:
        break
    AB = [x2-x1, y2-y1]
    BC = [x3-x2, y3-y2]
    CA = [x1-x3, y1-y3]
    BP = [xp-x2, yp-y2]
    CP = [xp-x3, yp-y3]
    AP = [xp-x1, yp-y1]
    v1 = AB[0]*BP[1]-AB[1]*BP[0]
    v2 = BC[0]*CP[1]-BC[1]*CP[0]
    v3 = CA[0]*AP[1]-CA[1]*AP[0]
    print(["NO", "YES"][(v1<0 and v2<0 and v3<0) or (v1>0 and v2>0 and v3>0)])