結果
| 問題 | No.105 arcの六角ボルト |
| ユーザー |
 Coki628
|
| 提出日時 | 2020-10-21 19:08:40 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 591 ms / 5,000 ms |
| コード長 | 7,079 bytes |
| コンパイル時間 | 493 ms |
| コンパイル使用メモリ | 82,432 KB |
| 実行使用メモリ | 93,568 KB |
| 最終ジャッジ日時 | 2024-07-21 08:58:52 |
| 合計ジャッジ時間 | 1,764 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
ソースコード
import sys
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10
class Geometry:
""" 幾何学計算用クラス """
def __init__(self, EPS):
self.EPS = EPS
def add(self, a, b):
x1, y1 = a
x2, y2 = b
return (x1+x2, y1+y2)
def sub(self, a, b):
x1, y1 = a
x2, y2 = b
return (x1-x2, y1-y2)
def mul(self, a, b):
x1, y1 = a
if not isinstance(b, tuple):
return (x1*b, y1*b)
x2, y2 = b
return (x1*x2, y1*y2)
def div(self, a, b):
x1, y1 = a
if not isinstance(b, tuple):
return (x1/b, y1/b)
x2, y2 = b
return (x1/x2, y1/y2)
def abs(self, a):
from math import hypot
x1, y1 = a
return hypot(x1, y1)
def norm(self, a):
x, y = a
return x**2 + y**2
def dot(self, a, b):
x1, y1 = a
x2, y2 = b
return x1*x2 + y1*y2
def cross(self, a, b):
x1, y1 = a
x2, y2 = b
return x1*y2 - y1*x2
def project(self, seg, p):
""" 線分segに対する点pの射影 """
p1, p2 = seg
base = self.sub(p2, p1)
r = self.dot(self.sub(p, p1), base) / self.norm(base)
return self.add(p1, self.mul(base, r))
def reflect(self, seg, p):
""" 線分segを対称軸とした点pの線対称の点 """
return self.add(p, self.mul(self.sub(self.project(seg, p), p), 2))
def ccw(self, p0, p1, p2):
""" 線分p0,p1から線分p0,p2への回転方向 """
a = self.sub(p1, p0)
b = self.sub(p2, p0)
# 反時計回り
if self.cross(a, b) > self.EPS: return 1
# 時計回り
if self.cross(a, b) < -self.EPS: return -1
# 直線上(p2 => p0 => p1)
if self.dot(a, b) < -self.EPS: return 2
# 直線上(p0 => p1 => p2)
if self.norm(a) < self.norm(b): return -2
# 直線上(p0 => p2 => p1)
return 0
def intersect(self, seg1, seg2):
""" 線分seg1と線分seg2の交差判定 """
p1, p2 = seg1
p3, p4 = seg2
return (
self.ccw(p1, p2, p3) * self.ccw(p1, p2, p4) <= 0
and self.ccw(p3, p4, p1) * self.ccw(p3, p4, p2) <= 0
)
def get_distance_PP(self, p1, p2):
from math import hypot
x1, y1 = p1
x2, y2 = p2
return hypot(x1-x2, y1-y2)
def get_distance_LP(self, line, p):
""" 直線lineと点pの距離 """
p1, p2 = line
return abs(self.cross(self.sub(p2, p1), self.sub(p, p1)) / self.abs(self.sub(p2, p1)))
def get_distance_SP(self, seg, p):
""" 線分segと点pの距離 """
p1, p2 = seg
if self.dot(self.sub(p2, p1), self.sub(p, p1)) < 0: return self.abs(self.sub(p, p1))
if self.dot(self.sub(p1, p2), self.sub(p, p2)) < 0: return self.abs(self.sub(p, p2))
return self.get_distance_LP(seg, p)
def get_distance_SS(self, seg1, seg2):
""" 線分seg1と線分seg2の距離 """
p1, p2 = seg1
p3, p4 = seg2
if self.intersect(seg1, seg2): return 0
return min(
self.get_distance_SP(seg1, p3), self.get_distance_SP(seg1, p4),
self.get_distance_SP(seg2, p1), self.get_distance_SP(seg2, p2),
)
def get_cross_pointSS(self, seg1, seg2):
""" 線分seg1と線分seg2の交点 """
p1, p2 = seg1
p3, p4 = seg2
if not self.intersect(seg1, seg2): return (INF, INF)
if p1 == p2: return p2
if p3 == p4: return p3
base = self.sub(p4, p3)
dist1 = abs(self.cross(base, self.sub(p1, p3)))
dist2 = abs(self.cross(base, self.sub(p2, p3)))
t = dist1 / (dist1+dist2)
return self.add(p1, self.mul(self.sub(p2, p1), t))
def intersectCL(self, c, line):
""" 円cと直線lineの交差判定 """
x, y, r = c
return self.get_distance_SP(line, (x, y)) <= r
def get_cross_pointCL(self, c, line):
""" 円cと直線lineの交点 """
from math import sqrt
if not self.intersectCL(c, line): return -1
x, y, r = c
p1, p2 = line
pr = self.project(line, (x, y))
e = self.div(self.sub(p2, p1), self.abs(self.sub(p2, p1)))
base = sqrt(r*r - self.norm(self.sub(pr, (x, y))))
return [self.add(pr, self.mul(e, base)), self.sub(pr, self.mul(e, base))]
def arg(self, p):
from math import atan2
x, y = p
return atan2(y, x)
def polar(self, a, r):
from math import sin, cos
return (cos(r)*a, sin(r)*a)
def intersectCC(self, c1, c2):
""" 円c1と円c2の交差判定 """
from math import hypot
x1, y1, r1 = c1
x2, y2, r2 = c2
return hypot(x1-x2, y1-y2) <= r1 + r2
def get_cross_pointCC(self, c1, c2):
""" 円c1と円c2の交点 """
from math import acos
if not self.intersectCC(c1, c2): return -1
x1, y1, r1 = c1
x2, y2, r2 = c2
try:
d = self.abs(self.sub((x1, y1), (x2, y2)))
a = acos((r1*r1+d*d-r2*r2) / (2*r1*d))
t = self.arg(self.sub((x2, y2), (x1, y1)))
return [self.add((x1, y1), self.polar(r1, t+a)), self.add((x1, y1), self.polar(r1, t-a))]
except:
# 一方が他方を内包しちゃってる場合等はここに飛ぶ(はず)
return -1
def get_degree(self, a, b, c):
""" ∠abcについて、反時計回り側の角度を取得 """
from math import degrees, atan2
# bから見たa,cへ向かうベクトル
v1 = self.sub(a, b)
x1, y1 = v1
v2 = self.sub(c, b)
x2, y2 = v2
# atan2がx=0から見た角度を返すので、差分を取る
res = degrees(atan2(y2, x2) - atan2(y1, x1))
if res < 0-self.EPS:
# 負の数なら時計回り側にあるので逆向きにする
res += 360
return res
for _ in range(INT()):
input()
gm = Geometry(EPS)
for i in range(6):
x, y = map(Decimal, input().split())
# (1, 0),(x, y)間の角度
res = gm.get_degree((1, 0), (0, 0), (x, y))
# 50度未満ならここがそうだとみなす
if 0 < res+EPS and res < 50-EPS:
print('{:.10f}'.format(res))