QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#614097#1079. Overlapping MapsdgddgdAC ✓22ms11180kbPython32.6kb2024-10-05 15:35:262024-10-05 15:35:26

Judging History

你现在查看的是最新测评结果

  • [2024-10-05 15:35:26]
  • 评测
  • 测评结果:AC
  • 用时:22ms
  • 内存:11180kb
  • [2024-10-05 15:35:26]
  • 提交

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