110 lines
2.4 KiB
Python
110 lines
2.4 KiB
Python
#!/usr/bin/env python
|
|
def read_input(input):
|
|
data = []
|
|
for line in input:
|
|
x, y, z, dx, dy, dz = [int(v) for v in line.replace("@", "").replace(",", " ").split()]
|
|
data.append((x,y,z,dx,dy,dz))
|
|
return data
|
|
|
|
def intersect_2d(l1, l2):
|
|
x0, y0, _, dx0, dy0, _ = l1
|
|
x1, y1, _, dx1, dy1, _ = l2
|
|
|
|
# convert to ax+by = c form
|
|
#(x - x0)dx0 + x0 = (y-y0)dy0 + y0
|
|
#x*dx0 - dx0*x0 + x0 = y*dy0 - dy0*y0 + y0
|
|
#x*dx0 - y*dy0 = dx0*x0 - dy0*y0 + y0 - x0
|
|
|
|
# x0 + t dx0 = x(t)
|
|
# y0 + t dy0 = y(t)
|
|
# t = (y - y0)/dy0
|
|
# t = (x - x0)/dx0
|
|
# (y-y0)/dy0 = (x-x0{
|
|
# x0 + (y-y0)/dy0 * dx0 = x
|
|
# x0 + y*dx0/dy0 - y0*dx0/dy0 = x
|
|
# x0 - y0*dx0/dy0 = x - y*dx0/dy0
|
|
|
|
a0 = dx0
|
|
b0 = -dy0
|
|
c0 = dx0*x0 - dy0*y0
|
|
|
|
a0 = dy0
|
|
b0 = -dx0
|
|
c0 = x0*(y0+dy0) - y0*(x0+dx0)
|
|
|
|
assert a0*x0 + b0*y0 == c0
|
|
|
|
a1 = dx1
|
|
b1 = -dy1
|
|
c1 = dx1*x1 - dy1*y1
|
|
|
|
a1 = dy1
|
|
b1 = -dx1
|
|
c1 = x1*(y1+dy1) - y1*(x1+dx1)
|
|
assert a1*x1 + b1*y1 == c1
|
|
|
|
# cramer's rule
|
|
d = a0*b1 - a1*b0
|
|
if d == 0 :
|
|
# non-intersecting
|
|
return None
|
|
|
|
return (c0*b1 - c1*b0)/d, (a0*c1 - a1*c0)/d
|
|
|
|
def intersect_2d(l1, l2):
|
|
x0, y0, _, dx0, dy0, _ = l1
|
|
x1, y1, _, dx1, dy1, _ = l2
|
|
|
|
# convert to ax+by = c form
|
|
# (x-x0)/dx0 = (y-y0)/dy0
|
|
# dy0(x-x0) = (dx0)(y-y0)
|
|
# x*dy0 - dy0*x0 = y*dx0 - dx0*y0
|
|
# x*dy0 - y*dx0 = dy0*x0 - dx0*y0
|
|
|
|
a0 = dy0
|
|
b0 = -dx0
|
|
c0 = x0*dy0 - y0*dx0
|
|
|
|
assert a0*x0 + b0*y0 == c0
|
|
|
|
a1 = dy1
|
|
b1 = -dx1
|
|
c1 = x1*dy1 - y1*dx1
|
|
assert a1*x1 + b1*y1 == c1
|
|
|
|
|
|
# cramer's rule
|
|
d = a0*b1 - a1*b0
|
|
if d == 0 :
|
|
# non-intersecting
|
|
return None
|
|
|
|
return (c0*b1 - c1*b0)/d, (a0*c1 - a1*c0)/d
|
|
|
|
def future(l1, point):
|
|
x,y,z, dx,dy,dz = l1
|
|
x0, y0 = point
|
|
return (dx < 0 and x0 <= x) or (dx > 0 and x0 >= x)
|
|
|
|
def inbounds(point):
|
|
x,y = point
|
|
if 7 <= x <= 21 and 7 <= y <= 21: return True
|
|
return 200000000000000 <= x <= 400000000000000 and 200000000000000 <= y <= 400000000000000
|
|
|
|
def solve(input):
|
|
data = read_input(input)
|
|
t = 0
|
|
for i,h1 in enumerate(data):
|
|
for h2 in data[i+1:]:
|
|
p = intersect_2d(h1, h2)
|
|
print(h1,h2, p)
|
|
if p is not None:
|
|
if future(h1, p) and future(h2, p):
|
|
if inbounds(p):
|
|
print(h1, h2, p)
|
|
t += 1
|
|
print(t)
|
|
|
|
import sys
|
|
solve(sys.stdin)
|