QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#708771#2458. Follow the Bouncing BallTenshi#WA 62ms11828kbPython34.2kb2024-11-04 06:15:072024-11-04 06:15:07

Judging History

This is the latest submission verdict.

  • [2024-11-04 06:15:07]
  • Judged
  • Verdict: WA
  • Time: 62ms
  • Memory: 11828kb
  • [2024-11-04 06:15:07]
  • Submitted

answer

from fractions import Fraction
def intersect(x1, y1, x2, y2, x3, y3, x4, y4): # segment, line
    d = ((x1-x2)*(y3-y4)  - (y1-y2)*(x3-x4))
    if d == 0:
        return False
    t = ((x1-x3)*(y3-y4) - (y1-y3)*(x3-x4)) / d
    return (x1 + t*(x2 - x1), y1 + t*(y2 - y1)) if  t >= 0 and t <= 1 else False

def reflect(x1, y1, x2, y2, x3, y3, x4, y4): # reflect first across second
    d1 = (x2 - x1) * (x4 - x3) + (y2 - y1) * (y4 - y3)
    d2 = (x4 - x3) * (x4 - x3) + (y4 - y3) * (y4 - y3)
    s = 2 * d1 / d2
    v2dx = s * (x4 - x3)
    v2dy = s * (y4 - y3)
    v1dx = (x2 - x1)
    v1dy = (y2 - y1)
    return (v2dx - v1dx), (v2dy - v1dy)

w, h, n, m, l, r, s = map(Fraction, input().split())
m = int(m)
n = int(n)

life = []
edges = [((0, 0), (0, h), -1), ((0, 0), (w, 0), -2), ((0, h), (w, h), -1), ((w, 0), (w, h), -1)]
shapes = []
for si in range(m):
    line = list(map(int, input().split()))
    p = line[0]
    i = 1
    verts = []
    for _ in range(p):
        verts.append((Fraction(line[i]), Fraction(line[i+1])))
        i += 2
    shapes.append([])
    for j in range(p):
        e = (verts[j], verts[(j+1)%p], si)
        edges.append(e)
        shapes[-1].append(e)
    q = line[i]
    i += 1
    life.append(q)

def raycast(x, y, dx, dy):
    global edges
    inters = []
    for e in edges:
        # print(e[0][0], e[0][1], '->', e[1][0], e[1][1], '   ', e[2])
        inter = intersect(e[0][0], e[0][1], e[1][0], e[1][1], x, y, x+dx, y+dy)
        # if inter == False:
        #     print('no inter')
        # elif ((inter[0] - x) * dx + (inter[1] - y) * dy) < 0.95:
        #     print("no dot")
        if inter and ((inter[0] - x) * dx + (inter[1] - y) * dy) > 0:
            inters.append((inter, e))
    
    inters.sort(key = lambda p: (p[0][0] - x)**2 + (p[0][1] - y)**2)
    point, edge = inters[0]
    r = reflect(point[0], point[1], point[0] + dx, point[1] + dy, edge[0][0], edge[0][1], edge[1][0], edge[1][1])
    return point[0], point[1], r[0], r[1], edge[2]


# print(raycast(10, 30, 1, -1))
# exit()
# print(reflect(0, 0, 1, 0, 0, 0, 3, 2))

# import matplotlib.pyplot as plt
# for e in edges:
#     plt.plot([e[0][0], e[1][0]], [e[0][1], e[1][1]])
# plt.show()

# shot = 0
# while shot < n:
#     hit = []
#     x = l
#     y = Fraction(0)
#     dx = r
#     dy = s
#     print(x, y)
#     while True:
#         nx, ny, dx, dy, i = raycast(x, y, dx, dy)
#         plt.plot([x, nx], [y, ny])
#         x = nx
#         y = ny
#         print(x, y, end = " ")
#         print(f"hit {i}")
#         if i == -2:
#             break
        
#         if i != -1:
#             life[i] -= 1
#             if life[i] <= 0:
#                 for e in edges:
#                     plt.plot([e[0][0], e[1][0]], [e[0][1], e[1][1]])
#                 for e in shapes[i]:
#                     edges.remove(e)
#                 print(shot, life)
#                 plt.show()
#                 plt.clf()
#     shot += 1
#     print()

import heapq
import math

events = []
for t in range(n):
    events.append((t, "spawn", None))

heapq.heapify(events)

x = l
y = Fraction(0)
dx = r
dy = s
while len(events) > 0:
    t, etype, info = heapq.heappop(events)
    if etype == "spawn":
        x = l
        y = Fraction(0)
        dx = r
        dy = s

        nx, ny, ndx, ndy, i = raycast(x, y, dx, dy)
        dt = math.sqrt((x - nx)**2 + (y-ny)**2)
        heapq.heappush(events, (t+dt, "hit", (nx, ny, ndx, ndy, i)))
    else:
        x, y, dx, dy, i = info
        if i == -2:
            continue
        
        if i != -1:
            if life[i] <= 0:
                continue
            life[i] -= 1
            if life[i] <= 0:
                # for e in edges:
                #     plt.plot([e[0][0], e[1][0]], [e[0][1], e[1][1]])
                for e in shapes[i]:
                    edges.remove(e)
                # plt.show()
                # plt.clf()
                # print(events)
                # print()
        
        nx, ny, ndx, ndy, i = raycast(x, y, dx, dy)
        dt = math.sqrt((x - nx)**2 + (y-ny)**2)
        heapq.heappush(events, (t+dt, "hit", (nx, ny, ndx, ndy, i)))


print(" ".join(map(str, life)))

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 24ms
memory: 11608kb

input:

20 30 5 3 10 -1 1
4 10 18 10 24 14 24 14 18 10
3 5 23 1 25 5 27 7
4 16 22 16 28 19 28 19 19 8

output:

0 2 3

result:

ok single line: '0 2 3'

Test #2:

score: 0
Accepted
time: 31ms
memory: 11828kb

input:

20 30 10 3 10.1 -1 1
4 10 18 10 24 14 24 14 18 10
3 5 23 1 25 5 27 7
4 16 22 16 28 19 28 19 19 8

output:

0 0 1

result:

ok single line: '0 0 1'

Test #3:

score: 0
Accepted
time: 53ms
memory: 11780kb

input:

40 100 90 4 10 0 1
3 5 10 5 20 35 20 100
3 5 40 35 40 35 30 100
3 5 50 5 60 35 60 100
3 5 80 35 80 35 70 100

output:

10 100 100 100

result:

ok single line: '10 100 100 100'

Test #4:

score: -100
Wrong Answer
time: 62ms
memory: 11732kb

input:

40 100 90 4 10 0 1
3 5 10 5 20 35 20 18
3 5 40 35 40 35 30 100
3 5 50 5 60 35 60 100
3 5 80 35 80 35 70 100

output:

0 39 100 100

result:

wrong answer 1st lines differ - expected: '0 27 100 100', found: '0 39 100 100'