結果
| 問題 | No.2602 Real Collider |
| ユーザー |
 strangerxxx
|
| 提出日時 | 2024-05-01 18:35:29 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 929 ms / 2,000 ms |
| コード長 | 6,439 bytes |
| コンパイル時間 | 390 ms |
| コンパイル使用メモリ | 82,304 KB |
| 実行使用メモリ | 83,624 KB |
| 最終ジャッジ日時 | 2024-11-22 00:27:02 |
| 合計ジャッジ時間 | 40,915 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 78 |
ソースコード
import math
def resolve():
import sys
input = sys.stdin.readline
q = int(input())
xa, ya, xb, yb, xc, yc = map(int, input().split())
x = (xa, ya)
y = (xb, yb)
z = (xc, yc)
try:
c = circumcenter2(x, y, z)
d = distance(c, (xa, ya))
except ZeroDivisionError:
c = (0, 0)
d = float("inf")
da = (
distance(x, y),
distance(y, z),
distance(z, x),
)
if da[0] >= da[1] + da[2]:
c = center(x, y)
d = distance(x, c)
elif da[1] >= da[2] + da[0]:
c = center(y, z)
d = distance(y, c)
elif da[2] >= da[0] + da[1]:
c = center(z, x)
d = distance(z, c)
for _ in range(q):
x, y = map(int, input().split())
print("Yes" if distance(c, (x, y)) <= d 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), Fraction(x1, y1)
if __name__ == "__main__":
resolve()