結果

問題 No.622 点と三角柱の内外判定
ユーザー mkawa2mkawa2
提出日時 2020-01-06 10:16:57
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 32 ms / 1,500 ms
コード長 1,972 bytes
コンパイル時間 91 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2024-05-02 10:43:22
合計ジャッジ時間 2,227 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 32 ms
11,136 KB
testcase_01 AC 32 ms
11,008 KB
testcase_02 AC 31 ms
10,880 KB
testcase_03 AC 31 ms
10,880 KB
testcase_04 AC 31 ms
11,008 KB
testcase_05 AC 31 ms
11,136 KB
testcase_06 AC 32 ms
11,136 KB
testcase_07 AC 31 ms
11,136 KB
testcase_08 AC 31 ms
11,136 KB
testcase_09 AC 31 ms
11,008 KB
testcase_10 AC 31 ms
11,008 KB
testcase_11 AC 31 ms
11,136 KB
testcase_12 AC 31 ms
11,008 KB
testcase_13 AC 31 ms
11,136 KB
testcase_14 AC 31 ms
11,136 KB
testcase_15 AC 32 ms
11,008 KB
testcase_16 AC 31 ms
11,008 KB
testcase_17 AC 31 ms
11,136 KB
testcase_18 AC 32 ms
11,136 KB
testcase_19 AC 32 ms
11,136 KB
testcase_20 AC 31 ms
10,880 KB
testcase_21 AC 31 ms
11,136 KB
testcase_22 AC 31 ms
11,008 KB
testcase_23 AC 31 ms
10,880 KB
testcase_24 AC 31 ms
11,136 KB
testcase_25 AC 31 ms
11,008 KB
testcase_26 AC 31 ms
11,136 KB
testcase_27 AC 31 ms
11,136 KB
testcase_28 AC 31 ms
11,136 KB
testcase_29 AC 32 ms
11,136 KB
testcase_30 AC 31 ms
11,008 KB
testcase_31 AC 31 ms
10,880 KB
権限があれば一括ダウンロードができます

ソースコード

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