どん底から這い上がるまでの記録

どん底から這い上がりたいけど這い上がれない人がいろいろ書くブログ(主にプログラミング)

0012: A Point in a Triangle

 

三角形と点

問題ページ

解き方

外積を利用する。 3つのベクトルが全て同じ方向を向いているとき、点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)])