QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#614097 | #1079. Overlapping Maps | dgddgd | AC ✓ | 22ms | 11180kb | Python3 | 2.6kb | 2024-10-05 15:35:26 | 2024-10-05 15:35:26 |
Judging History
answer
#7155 Overlapping Maps
# 틀렸습니다가 뜨기는 하는데... 솔직히 왜 그런건지는 잘 몰루겠네.
# 걍 ref로만 쓰자. Ray - Castling도 아직은 완전 X. 나중에 쓰기.
import sys
import math
input = sys.stdin.readline
def calc_circle_intersections(x1, y1, r1, x2, y2, r2):
d = math.sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1))
if d == 0:
if r1 == r2 :
return 'infinitely many intersections'
else:
return []
if d > r1 + r2 or d < abs(r1 - r2):
return []
a = (r1 * r1 - r2 * r2 + d * d) / 2 / d
h = math.sqrt(r1 * r1 - a * a)
# solve middle point
dx, dy = (x2-x1) / d, (y2-y1) / d
x0 = x1 + a * dx
y0 = y1 + a * dy
if d == r1 + r2:
return [(x0, y0)]
x3 = x0 - h * dy
y3 = y0 + h * dx
x4 = x0 + h * dy
y4 = y0 - h * dx
return [(x3, y3), (x4, y4)]
def apollonius_circle(x1, y1, x2, y2, k):
xc = (x1 - k*k * x2) / (1 - k*k)
yc = (y1 - k*k * y2) / (1 - k*k)
r = (k * math.sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1))) / abs(1 - k*k)
return xc, yc, r
def rotate_and_scale(x, y, r, s):
# 각도 r을 라디안으로 변환
theta = math.radians(r)
# 회전 및 스케일 적용
new_x = s / 100 * (x * math.cos(theta) - y * math.sin(theta))
new_y = s / 100 * (x * math.sin(theta) + y * math.cos(theta))
return new_x, new_y
PI = math.pi
while True:
w, h, x, y, s, r = map(int, input().split())
if (w, h, x, y, s, r) == (0, 0, 0, 0, 0, 0):
break
recpoint1 = (x + math.cos((r + 90) / 360 * 2 * PI) * h * s / 100, y + math.sin((r + 90) / 360 * 2 * PI) * h * s / 100)
recpoint2 = (x + math.cos((r) / 360 * 2 * PI) * h * s / 100, y + math.sin((r) / 360 * 2 * PI) * h * s / 100)
recpoint3 = (x + math.cos((r) / 360 * 2 * PI) * h * s / 100 + math.cos((r + 90) / 360 * 2 * PI) * h * s / 100, y + math.sin((r) / 360 * 2 * PI) * h * s / 100 + math.sin((r + 90) / 360 * 2 * PI) * h * s / 100)
coord = [(0, 0), (0, h), (x, y), recpoint1]
small_rec = [(x, y), recpoint1, recpoint3, recpoint2]
c1x, c1y, c1r = apollonius_circle(*coord[2], *coord[0], s / 100)
c2x, c2y, c2r = apollonius_circle(*coord[3], *coord[1], s / 100)
ans1, ans2 = calc_circle_intersections(c1x, c1y, c1r, c2x, c2y, c2r)
x1, y1 = ans1
dx, dy = rotate_and_scale(x1, y1, r, s)
if (round(x1, 2), round(y1, 2)) == (round(x+dx, 2), round(y+dy, 2)):
ans = ans1
else:
ans = ans2
print("%.2f %.2f" % (ans[0], ans[1]))
详细
Test #1:
score: 100
Accepted
time: 22ms
memory: 11180kb
input:
100 100 50 50 25 0 100 100 50 50 25 45 1000 1000 1 1 99 0 1000 1000 1 1 1 0 1000 1000 999 999 1 180 683 766 655 499 7 57 261 846 38 380 56 359 271 414 119 259 50 8 489 655 249 308 47 4 355 577 120 431 18 43 636 405 36 173 3 149 120 861 103 588 2 151 491 138 24 68 36 357 919 811 352 451 44 36 253 282...
output:
66.67 66.67 45.59 70.53 100.00 100.00 1.01 1.01 989.11 989.11 646.89 558.26 105.47 861.13 161.92 535.33 431.36 606.51 66.69 505.77 32.55 169.15 95.71 578.80 40.56 104.98 228.50 792.03 81.19 336.56 183.53 292.61 235.87 48.34 278.77 469.53 330.91 89.62 81.87 24.17 154.22 212.88 54.04 251.65 241.66 299...
result:
ok 455 lines