結果

問題 No.2602 Real Collider
ユーザー marc2825
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 64 WA * 13 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

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