Count queen attacks on points with blockers

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.

Part 1 — No blockers

For each point p in points, compute how many queens can attack p.

• A queen at 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].

Part 2 — Blockers (rocks)

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.

Input/Output

• Input: queens , points , and optionally rocks
• Output: integer array of size len(points)

Constraints (reasonable interview constraints)

• 1 <= len(queens), len(points), len(rocks) <= 2*10^5
• Coordinates fit in 32-bit signed integers.
• Aim for about O((Q + R + P) log(Q+R)) time for Part 2.