結果

問題 No.622 点と三角柱の内外判定
コンテスト
ユーザー mkawa2
提出日時 2020-01-06 10:16:57
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 34 ms / 1,500 ms
コード長 1,972 bytes
コンパイル時間 84 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2024-11-22 23:49:46
合計ジャッジ時間 2,326 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

sys.setrecursionlimit(10 ** 6)
from math import *
def MI(): return map(int, sys.stdin.readline().split())

def main():
    def rot(x, y, rad):
        x, y = x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad)
        return x, y

    def outer_sign(xyz0, xyz1, xyz2):
        x0, y0, _ = xyz0
        x1, y1, _ = xyz1
        x2, y2, _ = xyz2
        v1 = [x1 - x0, y1 - y0]
        v2 = [x2 - x0, y2 - y0]
        return v1[0] * v2[1] - v1[1] * v2[0] > 0

    pp = []
    for _ in range(4):
        x, y, z = MI()
        pp.append([x, y, z])
    # p0を原点に
    x0, y0, z0 = pp[0]
    for i in range(4):
        x, y, z = pp[i]
        pp[i] = [x - x0, y - y0, z - z0]
    # p1をxy平面に（z=0に）
    # x軸周りの回転移動、つまりyz平面に投影して考える
    # y=ycosθ-zsinθ,z=ysinθ+zcosθ
    x1, y1, z1 = pp[1]
    rad = -atan2(z1, y1)
    for i in range(1, 4):
        x, y, z = pp[i]
        y, z = rot(y, z, rad)
        pp[i] = [x, y, z]
    # print(pp)
    # 辺ABをx軸に
    # xy平面(z軸周り)で回転移動しp1がx軸上(y=0)に来るようにする
    x1, y1, z1 = pp[1]
    rad = -atan2(y1, x1)
    for i in range(1, 4):
        x, y, z = pp[i]
        x, y = rot(x, y, rad)
        pp[i] = [x, y, z]
    # print(pp)
    # p2をxy平面に（z=0に）
    # yz平面(x軸周り)の回転移動
    x2, y2, z2 = pp[2]
    rad = -atan2(z2, y2)
    for i in range(1, 4):
        x, y, z = pp[i]
        y, z = rot(y, z, rad)
        pp[i] = [x, y, z]
    pp[1][1] = 0
    # print(pp)
    # △ABCをxy平面に移動できたので、Dをxy平面に投影し、内部判定をする
    # →AB×→AD,→BC×→BD,→CA×→CDの正負が一致すれば、内部
    # http://www.thothchildren.com/chapter/5b267a436298160664e80763
    if outer_sign(pp[0], pp[1], pp[3]) == outer_sign(pp[1], pp[2], pp[3]) == outer_sign(pp[2], pp[0], pp[3]):
        print("YES")
    else:
        print("NO")

main()
0