結果
問題 | No.2602 Real Collider |
ユーザー |
![]() |
提出日時 | 2024-01-13 00:21:19 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,719 bytes |
コンパイル時間 | 319 ms |
コンパイル使用メモリ | 81,916 KB |
実行使用メモリ | 77,440 KB |
最終ジャッジ日時 | 2024-09-28 00:39:48 |
合計ジャッジ時間 | 11,941 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 WA * 44 |
ソースコード
def resolve():import sysinput = sys.stdin.readlineq = int(input())xa, ya, xb, yb, xc, yc = map(int, input().split())delta = 1e-14try:c = circumcenter((xa, ya), (xb, yb), (xc, yc))d = distance(c, (xa, ya)) + deltaexcept ValueError:a = sorted([xa, xb, xc])b = sorted([ya, yb, yc])if xa != xc:d = (a[-1] - a[0]) / 2 + deltac = (a[0] + d, b[0])else:d = (b[-1] - b[0]) / 2 + deltac = (a[0], b[0] + d)for _ in range(q):x, y = map(int, 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 + gcreturn [(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) / 2return (s * (s - a) * (s - b) * (s - c)) ** 0.5def sin_a(a, b, c):# sin∠BACs = area(a, b, c)return max(min(s * 2 / b / c, 1), -1)def cos_a(a, b, c):# cos∠BACreturn max(min((b**2 + c**2 - a**2) / (2 * b * c), 1), -1)def sin_o(pa, pb):# sin∠AOBa, b, c = side_length([0] * len(pa), pa, pb)return sin_a(a, b, c)def cos_o(pa, pb):# cos∠AOBa, b, c = side_length([0] * len(pa), pa, pb)return cos_a(a, b, c)def sin_t(pa, pb, pc):# 3つの角のsina, b, c = side_length(pa, pb, pc)s = area(a, b, c)return s * 2 / b / c, s * 2 / c / a, s * 2 / a / bdef cos_t(pa, pb, pc):# 3つの角のcosa, 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)]) ** 0.5def midpoint(pa, pb):return [(x + y) / 2 for x, y in zip(pa, pb)]if __name__ == "__main__":resolve()