結果

問題 No.2602 Real Collider
ユーザー marc2825marc2825
提出日時 2024-01-12 22:32:46
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,521 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 94,760 KB
最終ジャッジ日時 2024-01-12 22:32:53
合計ジャッジ時間 6,107 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 144 ms
94,376 KB
testcase_01 AC 154 ms
87,572 KB
testcase_02 AC 140 ms
87,572 KB
testcase_03 AC 151 ms
88,084 KB
testcase_04 AC 143 ms
87,700 KB
testcase_05 AC 139 ms
87,572 KB
testcase_06 AC 142 ms
87,700 KB
testcase_07 AC 140 ms
87,700 KB
testcase_08 AC 153 ms
87,700 KB
testcase_09 AC 142 ms
87,700 KB
testcase_10 TLE -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
testcase_52 -- -
testcase_53 -- -
testcase_54 -- -
testcase_55 -- -
testcase_56 -- -
testcase_57 -- -
testcase_58 -- -
testcase_59 -- -
testcase_60 -- -
testcase_61 -- -
testcase_62 -- -
testcase_63 -- -
testcase_64 -- -
testcase_65 -- -
testcase_66 -- -
testcase_67 -- -
testcase_68 -- -
testcase_69 -- -
testcase_70 -- -
testcase_71 -- -
testcase_72 -- -
testcase_73 -- -
testcase_74 -- -
testcase_75 -- -
testcase_76 -- -
testcase_77 -- -
testcase_78 -- -
testcase_79 -- -
testcase_80 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from fractions import Fraction


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


class Fractionll:
    def __init__(self, x=0, y=1):
        self.x = x
        self.y = y
        self.reduc()

    def reduc(self):
        minus = 1
        absx = self.x
        absy = self.y
        if self.x < 0:
            minus *= -1
            absx *= -1
        if self.y < 0:
            minus *= -1
            absy *= -1
        g = gcd(absx, absy)
        self.x = minus * absx // g
        self.y = absy // g

    def __lt__(self, other):
        return self.x * other.y < self.y * other.x

    def __le__(self, other):
        return self.x * other.y <= self.y * other.x

    def __gt__(self, other):
        return self.x * other.y > self.y * other.x

    def __ge__(self, other):
        return self.x * other.y >= self.y * other.x

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __neg__(self):
        return Fractionll(-self.x, self.y)

    def __iadd__(self, other):
        self.x = self.x * other.y + self.y * other.x
        self.y *= other.y
        self.reduc()
        return self

    def __add__(self, other):
        return Fractionll(self.x, self.y).__iadd__(other)

    def __isub__(self, other):
        self.x = self.x * other.y - self.y * other.x
        self.y *= other.y
        self.reduc()
        return self

    def __sub__(self, other):
        return Fractionll(self.x, self.y).__isub__(other)

    def __imul__(self, other):
        self.x *= other.x
        self.y *= other.y
        self.reduc()
        return self

    def __mul__(self, other):
        return Fractionll(self.x, self.y).__imul__(other)

    def __itruediv__(self, other):
        self.x *= other.y
        self.y *= other.x
        self.reduc()
        return self

    def __truediv__(self, other):
        return Fractionll(self.x, self.y).__itruediv__(other)

    def inv(self):
        return Fractionll(self.y, self.x)

    def pow(self, t):
        if t < 0:
            return self.inv().pow(-t)
        a, d = Fractionll(1, 1), self
        while t:
            d *= d
            if t & 1:
                a *= d
            t >>= 1
        return a

    def __str__(self):
        return f"{self.x}/{self.y}"


def solve():
    Q = int(input())
    X = [0] * 3
    Y = [0] * 3
    X[0], Y[0], X[1], Y[1], X[2], Y[2] = map(int, input().split())

    a = X[0] - X[1]
    b = Y[0] - Y[1]
    c = X[1] - X[2]
    d = Y[1] - Y[2]
    bunbo = 2 * (a * d - b * c)

    if bunbo == 0:
        XY = sorted([(X[i], Y[i]) for i in range(3)])
        cx, cy = XY[1][0], XY[1][1]
        r2 = (X[0] - cx) ** 2 + (Y[0] - cy) ** 2

        for _ in range(Q):
            x, y = map(int, input().split())
            dist = (x - cx) ** 2 + (y - cy) ** 2
            print("Yes" if dist <= r2 else "No")
        return

    e = X[0] ** 2 + Y[0] ** 2 - (X[1] ** 2 + Y[1] ** 2)
    f = X[1] ** 2 + Y[1] ** 2 - (X[2] ** 2 + Y[2] ** 2)

    cx = Fractionll(d * e - b * f, bunbo)
    cy = Fractionll(-c * e + a * f, bunbo)
    r2 = (Fractionll(X[0], 1) - cx) * (Fractionll(X[0], 1) - cx) + (Fractionll(Y[0], 1) - cy) * (Fractionll(Y[0], 1) - cy)
    #print(cx.x,cx.y,cy.x,cy.y,r2)

    for _ in range(Q):
        x, y = map(int, input().split())
        dist = (Fractionll(x, 1) - cx) * (Fractionll(x, 1) - cx) + (Fractionll(y, 1) - cy) * (Fractionll(y, 1) - cy)
        #p = dist.x * r2.y
        #q = dist.y * r2.x
        print("Yes" if dist <= r2 else "No")

solve()
0