QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#708771 | #2458. Follow the Bouncing Ball | Tenshi# | WA | 62ms | 11828kb | Python3 | 4.2kb | 2024-11-04 06:15:07 | 2024-11-04 06:15:07 |
Judging History
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'