結果
| 問題 | No.2602 Real Collider |
| ユーザー |
 strangerxxx
|
| 提出日時 | 2024-01-20 14:23:48 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,789 bytes |
| コンパイル時間 | 274 ms |
| コンパイル使用メモリ | 81,700 KB |
| 実行使用メモリ | 92,900 KB |
| 最終ジャッジ日時 | 2024-01-20 14:23:56 |
| 合計ジャッジ時間 | 7,826 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 146 ms
87,652 KB |
| testcase_01 | AC | 124 ms
79,184 KB |
| testcase_02 | AC | 132 ms
80,464 KB |
| testcase_03 | AC | 341 ms
81,744 KB |
| testcase_04 | AC | 141 ms
80,976 KB |
| testcase_05 | AC | 168 ms
80,976 KB |
| testcase_06 | AC | 139 ms
80,976 KB |
| testcase_07 | AC | 143 ms
80,976 KB |
| testcase_08 | AC | 141 ms
80,976 KB |
| testcase_09 | AC | 140 ms
80,848 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 | -- | - |
ソースコード
from decimal import Decimal
def resolve():
import sys
input = sys.stdin.readline
q = int(input())
xa, ya, xb, yb, xc, yc = map(Decimal, input().split())
delta = Decimal(1e-14)
try:
c = circumcenter((xa, ya), (xb, yb), (xc, yc))
d = distance(c, (xa, ya)) + delta
except ValueError:
a = sorted([xa, xb, xc])
b = sorted([ya, yb, yc])
if xa != xc:
d = (a[-1] - a[0]) / 2 + delta
c = (a[0] + d, b[0])
else:
d = (b[-1] - b[0]) / 2 + delta
c = (a[0], b[0] + d)
for _ in range(q):
x, y = map(Decimal, input().split())
# print(distance(c, (x, y)), d)
print("Yes" if distance(c, (x, y)) <= d else "No")
def circumcenter(pa, pb, pc, ignore=False):
# 外心
a, b, c = side_length(pa, pb, pc)
try:
return barycentric_coordinate(
pa,
pb,
pc,
sin_a(a, b, c) * cos_a(a, b, c),
sin_a(b, c, a) * cos_a(b, c, a),
sin_a(c, a, b) * cos_a(c, a, b),
ignore,
)
except:
if ignore:
return []
else:
raise ValueError("points on a straight line")
def barycentric_coordinate(pa, pb, pc, ga, gb, gc, ignore=False):
# △BCP:△CAP:△ABP=ga:gb:gcであるときの点Pの座標
try:
g = ga + gb + gc
return [(a * ga + b * gb + c * gc) / g for a, b, c in zip(pa, pb, pc)]
except:
if ignore:
return []
else:
raise ValueError("points on a straight line")
def side_length(pa, pb, pc):
# 3辺の長さ
return distance(pc, pb), distance(pa, pc), distance(pa, pb)
def area(a, b, c):
# 面積
s = (a + b + c) / 2
return (s * (s - a) * (s - b) * (s - c)) ** Decimal("0.5")
def sin_a(a, b, c):
# sin∠BAC
s = area(a, b, c)
return max(min(s * 2 / b / c, 1), -1)
def cos_a(a, b, c):
# cos∠BAC
return max(min((b**2 + c**2 - a**2) / (2 * b * c), 1), -1)
def sin_o(pa, pb):
# sin∠AOB
a, b, c = side_length([0] * len(pa), pa, pb)
return sin_a(a, b, c)
def cos_o(pa, pb):
# cos∠AOB
a, b, c = side_length([0] * len(pa), pa, pb)
return cos_a(a, b, c)
def sin_t(pa, pb, pc):
# 3つの角のsin
a, b, c = side_length(pa, pb, pc)
s = area(a, b, c)
return s * 2 / b / c, s * 2 / c / a, s * 2 / a / b
def cos_t(pa, pb, pc):
# 3つの角のcos
a, b, c = side_length(pa, pb, pc)
return cos_a(a, b, c), cos_a(b, c, a), cos_a(c, a, b)
def distance(pa, pb):
return sum([(i - j) ** 2 for i, j in zip(pa, pb)]) ** Decimal("0.5")
def midpoint(pa, pb):
return [(x + y) / 2 for x, y in zip(pa, pb)]
if __name__ == "__main__":
resolve()