結果
| 問題 | No.2602 Real Collider |
| ユーザー |
 strangerxxx
|
| 提出日時 | 2024-05-01 18:17:22 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,889 bytes |
| コンパイル時間 | 192 ms |
| コンパイル使用メモリ | 82,304 KB |
| 実行使用メモリ | 85,024 KB |
| 最終ジャッジ日時 | 2024-11-21 23:58:19 |
| 合計ジャッジ時間 | 55,455 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 44 ms
54,016 KB |
| testcase_01 | AC | 43 ms
53,632 KB |
| testcase_02 | AC | 41 ms
53,980 KB |
| testcase_03 | AC | 46 ms
56,064 KB |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | AC | 213 ms
77,580 KB |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | AC | 234 ms
77,464 KB |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | AC | 258 ms
77,808 KB |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
| testcase_40 | WA | - |
| testcase_41 | WA | - |
| testcase_42 | WA | - |
| testcase_43 | WA | - |
| testcase_44 | WA | - |
| testcase_45 | WA | - |
| testcase_46 | WA | - |
| testcase_47 | WA | - |
| testcase_48 | WA | - |
| testcase_49 | WA | - |
| testcase_50 | WA | - |
| testcase_51 | WA | - |
| testcase_52 | WA | - |
| testcase_53 | WA | - |
| testcase_54 | WA | - |
| testcase_55 | WA | - |
| testcase_56 | WA | - |
| testcase_57 | WA | - |
| testcase_58 | WA | - |
| testcase_59 | WA | - |
| testcase_60 | WA | - |
| testcase_61 | WA | - |
| testcase_62 | WA | - |
| testcase_63 | WA | - |
| testcase_64 | WA | - |
| testcase_65 | WA | - |
| testcase_66 | WA | - |
| testcase_67 | WA | - |
| testcase_68 | WA | - |
| testcase_69 | WA | - |
| testcase_70 | WA | - |
| testcase_71 | WA | - |
| testcase_72 | WA | - |
| testcase_73 | WA | - |
| testcase_74 | WA | - |
| testcase_75 | WA | - |
| testcase_76 | WA | - |
| testcase_77 | WA | - |
| testcase_78 | WA | - |
| testcase_79 | WA | - |
| testcase_80 | WA | - |
ソースコード
import math
def resolve():
import sys
input = sys.stdin.readline
q = int(input())
xa, ya, xb, yb, xc, yc = map(int, input().split())
if islinear((xa, ya), (xb, yb), (xc, yc)):
x = (xa, ya)
y = (xb, yb)
z = (xc, yc)
d = (
distance(x, y),
distance(y, z),
distance(z, x),
)
mx = max(d)
if d[0] == mx:
c = center(x, y)
d = distance(x, c)
elif d[1] == mx:
c = center(y, z)
d = distance(y, c)
else:
c = center(z, x)
d = distance(z, c)
else:
for x, y, z in (
((xa, ya), (xb, yb), (xc, yc)),
((xb, yb), (xc, yc), (xa, ya)),
((xc, yc), (xa, ya), (xb, yb)),
):
if distance(x, y) >= distance(y, z) + distance(z, x):
c = center(x, y)
d = Fraction(distance(x, y), 2)
break
else:
c = circumcenter2((xa, ya), (xb, yb), (xc, yc))
d = distance(c, (xa, ya))
for _ in range(q):
x, y = map(int, input().split())
print("Yes" if distance(c, (x, y)) <= d**2 else "No")
class Fraction:
def __init__(self, a: int = 0, b: int = 1) -> None:
if isinstance(a, Fraction):
self.a, self.b = a.a, a.b
return
a, b = int(a), int(b)
if b == 0:
raise ZeroDivisionError(f"{a}/{b}")
if b < 0:
a, b = -a, -b
self.a, self.b = a, b
self._reducion()
def _reducion(self):
g = math.gcd(self.a, self.b)
self.a //= g
self.b //= g
def __add__(self, other):
if isinstance(other, Fraction):
g = math.gcd(self.b, other.b)
x = other.b // g * self.a
y = self.b // g * other.a
return Fraction(x + y, self.b // g * other.b)
return Fraction(self.a + other * self.b, self.b)
def __iadd__(self, other):
if isinstance(other, Fraction):
g = math.gcd(self.b, other.b)
self.a *= other.b // g
self.a += self.b // g * other.a
self.b *= other.b // g
else:
self.a += other * self.b
self._reducion()
return self
__radd__ = __add__
def __sub__(self, other):
if isinstance(other, Fraction):
return self.__add__(-other)
return self.__add__(-other)
def __isub__(self, other):
if isinstance(other, Fraction):
return self.__iadd__(-other.a, other.b)
return self.__iadd__(-other)
def __rsub__(self, other):
return -self + other
def __mul__(self, other):
if isinstance(other, Fraction):
return Fraction(self.a * other.a, self.b * other.b)
else:
return Fraction(self.a * other, self.b)
def __imul__(self, other):
if isinstance(other, Fraction):
self.a *= other.a
self.b *= other.b
else:
self.a *= other
self._reducion()
return self
__rmul__ = __mul__
def __floordiv__(self, other):
if isinstance(other, Fraction):
return self.__mul__(other.inverse())
return Fraction(self.a, self.b * other)
def __ifloordiv__(self, other):
if isinstance(other, Fraction):
return self.__imul__(other.inverse())
self.b *= other
self._reducion()
return self
def __rfloordiv__(self, other):
return self.inverse() * other
__truediv__ = __floordiv__
__itruediv__ = __ifloordiv__
__rtruediv__ = __rfloordiv__
def __pow__(self, other):
if isinstance(other, Fraction):
if other.b == 1:
return self.__pow__(other.a)
raise NotImplementedError
return Fraction(self.a**other, self.b**other)
def __ipow__(self, other):
if isinstance(other, Fraction):
if other.b == 1:
return self.__ipow__(other.a)
raise NotImplementedError
self.a **= other
self.b **= other
return self
def __rpow__(self, other):
if self.b != 1:
raise NotImplementedError
return other**self.a
def __floor__(self) -> int:
return self.a // self.b
def __ceil__(self) -> int:
return (self.a + self.b - 1) // self.b
__int__ = __floor__
def __float__(self):
return self.a / self.b
def inverse(self):
if self.a == 0:
raise ZeroDivisionError(f"tring to calcuate inverse of {self.a}/{self.b}")
return Fraction(self.b, self.a)
def __pos__(self):
return Fraction(self.a, self.b)
def __neg__(self):
return Fraction(-self.a, self.b)
def __abs__(self):
return Fraction(abs(self.a), self.b)
def __eq__(self, other) -> bool:
if isinstance(other, Fraction):
return self.a == other.a and self.b == other.b
return self.a == self.b * other
def __gt__(self, other):
if isinstance(other, Fraction):
return self.a * other.b > other.a * self.b
return self.a > self.b * other
def __ge__(self, other):
if isinstance(other, Fraction):
return self.a * other.b >= other.a * self.b
return self.a >= self.b * other
def __lt__(self, other):
if isinstance(other, Fraction):
return self.a * other.b < other.a * self.b
return self.a < self.b * other
def __le__(self, other):
if isinstance(other, Fraction):
return self.a * other.b <= other.a * self.b
return self.a <= self.b * other
def __str__(self) -> str:
return f"{self.a}/{self.b}"
__repr__ = __str__
def __hash__(self) -> int:
return hash(self.__str__())
def distance(pa, pb):
return sum([(i - j) ** 2 for i, j in zip(pa, pb)])
def islinear(pa, pb, pc):
return (pa[0] - pb[0]) * (pa[1] - pc[1]) == (pa[0] - pc[0]) * (pa[1] - pb[1])
def center(x, y):
return (Fraction((x[0] + y[0]), 2), Fraction((x[1] + y[1]), 2))
def circumcenter2(pa, pb, pc):
# 外心
x0 = (
(pa[0] ** 2 + pa[1] ** 2) * (pb[1] - pc[1])
+ (pb[0] ** 2 + pb[1] ** 2) * (pc[1] - pa[1])
+ (pc[0] ** 2 + pc[1] ** 2) * (pa[1] - pb[1])
)
y0 = 2 * ((pb[1] - pc[1]) * (pa[0] - pb[0]) - (pa[1] - pb[1]) * (pb[0] - pc[0]))
x1 = (
(pa[0] ** 2 + pa[1] ** 2) * (pb[0] - pc[0])
+ (pb[0] ** 2 + pb[1] ** 2) * (pc[0] - pa[0])
+ (pc[0] ** 2 + pc[1] ** 2) * (pa[0] - pb[0])
)
y1 = 2 * ((pb[0] - pc[0]) * (pa[1] - pb[1]) - (pa[0] - pb[0]) * (pb[1] - pc[1]))
return (
Fraction(x0, y0) if y0 else 0,
Fraction(x1, y1) if y1 else 0,
)
if __name__ == "__main__":
resolve()