結果

問題 No.2602 Real Collider
ユーザー marc2825marc2825
提出日時 2024-01-12 22:32:46
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,521 bytes
コンパイル時間 282 ms
コンパイル使用メモリ 82,472 KB
実行使用メモリ 95,208 KB
最終ジャッジ日時 2024-09-27 23:11:02
合計ジャッジ時間 6,380 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 118 ms
88,332 KB
testcase_01 AC 116 ms
88,300 KB
testcase_02 AC 116 ms
88,224 KB
testcase_03 AC 135 ms
88,416 KB
testcase_04 AC 121 ms
88,160 KB
testcase_05 AC 120 ms
88,112 KB
testcase_06 AC 122 ms
88,568 KB
testcase_07 AC 122 ms
88,484 KB
testcase_08 AC 123 ms
88,480 KB
testcase_09 AC 128 ms
88,276 KB
testcase_10 TLE -
testcase_11 AC 1,084 ms
93,608 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 897 ms
91,512 KB
testcase_16 AC 1,270 ms
93,796 KB
testcase_17 AC 1,441 ms
94,476 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 1,424 ms
94,428 KB
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 AC 735 ms
90,820 KB
testcase_27 WA -
testcase_28 AC 1,072 ms
92,372 KB
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 1,383 ms
92,256 KB
testcase_32 AC 1,149 ms
93,276 KB
testcase_33 AC 1,403 ms
92,016 KB
testcase_34 AC 1,291 ms
94,732 KB
testcase_35 AC 933 ms
91,044 KB
testcase_36 AC 710 ms
91,016 KB
testcase_37 AC 1,451 ms
92,036 KB
testcase_38 AC 1,434 ms
93,368 KB
testcase_39 AC 1,426 ms
92,160 KB
testcase_40 AC 792 ms
91,068 KB
testcase_41 AC 1,495 ms
92,596 KB
testcase_42 AC 1,270 ms
93,996 KB
testcase_43 AC 1,105 ms
92,916 KB
testcase_44 AC 1,559 ms
93,324 KB
testcase_45 AC 1,025 ms
92,936 KB
testcase_46 AC 1,079 ms
92,196 KB
testcase_47 AC 1,448 ms
92,732 KB
testcase_48 AC 1,144 ms
92,408 KB
testcase_49 AC 1,026 ms
91,580 KB
testcase_50 AC 825 ms
93,236 KB
testcase_51 AC 875 ms
91,732 KB
testcase_52 AC 648 ms
91,288 KB
testcase_53 AC 1,466 ms
92,364 KB
testcase_54 AC 1,312 ms
92,668 KB
testcase_55 AC 1,179 ms
94,116 KB
testcase_56 AC 1,110 ms
92,940 KB
testcase_57 AC 1,042 ms
92,548 KB
testcase_58 AC 559 ms
92,980 KB
testcase_59 AC 1,402 ms
91,796 KB
testcase_60 AC 1,033 ms
92,588 KB
testcase_61 AC 962 ms
93,908 KB
testcase_62 AC 1,271 ms
93,140 KB
testcase_63 AC 1,328 ms
94,300 KB
testcase_64 AC 1,658 ms
92,052 KB
testcase_65 AC 886 ms
94,632 KB
testcase_66 AC 1,368 ms
94,272 KB
testcase_67 AC 746 ms
92,684 KB
testcase_68 AC 818 ms
93,044 KB
testcase_69 AC 654 ms
92,524 KB
testcase_70 AC 775 ms
92,532 KB
testcase_71 AC 926 ms
91,156 KB
testcase_72 AC 1,229 ms
93,512 KB
testcase_73 AC 1,098 ms
94,136 KB
testcase_74 AC 1,374 ms
92,544 KB
testcase_75 AC 1,340 ms
94,220 KB
testcase_76 AC 1,245 ms
92,240 KB
testcase_77 AC 1,238 ms
93,244 KB
testcase_78 AC 1,534 ms
93,828 KB
testcase_79 AC 1,277 ms
95,208 KB
testcase_80 AC 1,370 ms
94,084 KB
権限があれば一括ダウンロードができます

ソースコード

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