You are given positions on an (unbounded) 2D integer grid.
queens
: coordinates of queens
points
: query coordinates
A queen attacks along 8 directions: horizontal, vertical, and the two diagonals.
For each point p in points, compute how many queens can attack p.
q
attacks
p
if
p
lies on the same row, column, or diagonal as
q
.
Return an array ans where ans[i] is the number of queens attacking points[i].
Now you are also given:
rocks
: coordinates of rocks
Rocks block attacks. A queen attacks a point p only if, along the line from the queen to p, there is no rock strictly between them.
Again return ans[i] for each query point.
queens
,
points
, and optionally
rocks
len(points)
1 <= len(queens), len(points), len(rocks) <= 2*10^5
O((Q + R + P) log(Q+R))
time for Part 2.