結果

問題 No.2564 衝突予測
ユーザー とろちゃとろちゃ
提出日時 2023-12-02 15:52:25
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 534 ms / 2,000 ms
コード長 3,171 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 81,860 KB
最終ジャッジ日時 2023-12-02 15:52:31
合計ジャッジ時間 5,758 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,460 KB
testcase_01 AC 40 ms
53,460 KB
testcase_02 AC 36 ms
53,460 KB
testcase_03 AC 435 ms
81,128 KB
testcase_04 AC 427 ms
81,160 KB
testcase_05 AC 436 ms
79,896 KB
testcase_06 AC 450 ms
79,448 KB
testcase_07 AC 418 ms
79,016 KB
testcase_08 AC 424 ms
80,808 KB
testcase_09 AC 512 ms
81,860 KB
testcase_10 AC 493 ms
81,732 KB
testcase_11 AC 534 ms
81,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# import pypyjit;pypyjit.set_param("max_unroll_recursion=-1")
import os
import sys

# from bisect import *
# from collections import *
# from datetime import *
# from decimal import *  # PyPyだと遅い
# from heapq import *
# from itertools import *
# from math import gcd, lcm
# from random import *
# from string import *

# import numpy as np
# from atcoder.dsu import *
# from atcoder.segtree import *
# from more_itertools import *
# from sortedcontainers import *

# sys.setrecursionlimit(10**7)  # PyPyは呪文を付ける
# sys.set_int_max_str_digits(0)
INF = 1 << 61
MOD = 998244353
# MOD = 10**9 + 7
IS_ATCODER = os.getenv("ATCODER", 0)

File = sys.stdin


def input():
    return File.readline().replace("\n", "")


# ///////////////////////////////////////////////////////////////////////////
def find_intersection(line1, line2):
    x1, y1 = line1[0]
    x2, y2 = line1[1]
    x3, y3 = line2[0]
    x4, y4 = line2[1]

    denominator = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)

    if denominator == 0:
        # 直線が平行の場合
        return None

    x = (
        (x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)
    ) / denominator
    y = (
        (x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)
    ) / denominator

    return (x, y)


def max_min_cross(p1, p2, p3, p4):
    min_ab, max_ab = min(p1, p2), max(p1, p2)
    min_cd, max_cd = min(p3, p4), max(p3, p4)

    if min_ab > max_cd or max_ab < min_cd:
        return False

    return True


def cross_judge(a, b, c, d):
    # x座標による判定
    if not max_min_cross(a[0], b[0], c[0], d[0]):
        return False

    # y座標による判定
    if not max_min_cross(a[1], b[1], c[1], d[1]):
        return False

    tc1 = (a[0] - b[0]) * (c[1] - a[1]) + (a[1] - b[1]) * (a[0] - c[0])
    tc2 = (a[0] - b[0]) * (d[1] - a[1]) + (a[1] - b[1]) * (a[0] - d[0])
    td1 = (c[0] - d[0]) * (a[1] - c[1]) + (c[1] - d[1]) * (c[0] - a[0])
    td2 = (c[0] - d[0]) * (b[1] - c[1]) + (c[1] - d[1]) * (c[0] - b[0])
    return tc1 * tc2 <= 0 and td1 * td2 <= 0


DIR = {"U": (0, INF), "D": (0, -INF), "L": (-INF, 0), "R": (INF, 0)}

for _ in range(int(input())):
    x1, y1, d1 = input().split()
    x2, y2, d2 = input().split()
    x1, y1, x2, y2 = int(x1), int(y1), int(x2), int(y2)

    line1 = [(x1, y1), (x1 + DIR[d1][0], y1 + DIR[d1][1])]
    line2 = [(x2, y2), (x2 + DIR[d2][0], y2 + DIR[d2][1])]
    res = find_intersection(line1, line2)
    if res is None:
        if x1 == x2:
            if y1 < y2:
                print("Yes" if d1 == "U" and d2 == "D" else "No")
            else:
                print("Yes" if d1 == "D" and d2 == "U" else "No")
        elif y1 == y2:
            if x1 < x2:
                print("Yes" if d1 == "R" and d2 == "L" else "No")
            else:
                print("Yes" if d1 == "L" and d2 == "R" else "No")
        else:
            print("No")
    else:
        if not cross_judge(*line1, *line2):
            print("No")
            continue
        dist1 = abs(res[0] - x1) + abs(res[1] - y1)
        dist2 = abs(res[0] - x2) + abs(res[1] - y2)
        print("Yes" if dist1 == dist2 else "No")
0