Good Robot Paths

We need count ordered pairs of black points $(a,b)$ such that every integer point on any shortest robot path from $a$ to $b$ is black.

The important deconstruction: this is not asking for “there exists a clean shortest path”. It says any shortest path. That is way stricter.

Suppose $a=(x_1,y_1)$ and $b=(x_2,y_2)$, with $x_1\le x_2$ and $y_1\le y_2$. A shortest path uses exactly $x_2-x_1$ right moves and $y_2-y_1$ up moves, in any order. For any integer point $(x,y)$ inside the rectangle

$$[x_1,x_2]\times [y_1,y_2],$$

there is some shortest path that visits it: go to $(x,y)$ first, then finish. So the union of all shortest paths is the whole rectangle.

Therefore a pair is good iff its closed axis-aligned integer rectangle is completely black.

That one sentence is the whole problem. The rest is making it fast enough without summoning quadratic hell.

Degenerate rectangles

If two points are on the same row, we only need the horizontal segment between them to be fully black. On each row, sort all $x$ values. Every maximal run of consecutive integers of length $L$ contributes

$$L(L-1)$$

ordered pairs.

Same for columns, using sorted $y$ values.

These handle width $0$ or height $0$.

Real rectangles

Now consider rectangles with positive width and height.

A rectangle from rows $y_l$ to $y_r$ is possible only if every row between them exists and is consecutive. If there is a missing row, the rectangle would contain white points. So we split the grid into blocks of consecutive occupied row numbers. Different blocks never interact for non-degenerate rectangles.

Inside one block of consecutive rows, store for each row the sorted set of black columns on that row.

For a fixed row interval $[l,r]$, the columns that can be used by a full rectangle are exactly

$$C_{l,r}=row_l\cap row_{l+1}\cap\cdots\cap row_r.$$

If a column is missing from one of these rows, any rectangle using that column has a white point. Among the common columns, we also need consecutive columns. If $C_{l,r}$ has a maximal consecutive run of length $L$, then choosing two different columns from this run gives a positive-width full rectangle over rows $l..r$.

For each unordered pair of columns, there are exactly two ordered endpoint pairs with positive slope/negative slope corners? More directly: if columns are $x_1<x_2$ and rows are $y_l<y_r$, the good ordered pairs are

$$(x_1,y_l)\to(x_2,y_r),\quad (x_2,y_r)\to(x_1,y_l),$$ $$(x_1,y_r)\to(x_2,y_l),\quad (x_2,y_l)\to(x_1,y_r).$$

So every unordered column pair contributes $4$. Since $\binom L2$ unordered pairs live inside a run, the contribution is

$$4\binom L2 = 2L(L-1).$$

But if we count ordered column choices directly, that is $L(L-1)$, and then multiply by $2$ for the two choices of row direction. Same thing.

Avoiding too much work

Naively intersecting all row intervals is too slow. The useful trick is to enumerate from each starting row and maintain the current intersection as a sorted vector. Intersect the current vector with the next row. The intersection size can only shrink.

The total work is acceptable if we always intersect sorted vectors linearly and stop when the intersection becomes smaller than $2$, because then no positive-width rectangle can remain.

Why does this pass? A point can only survive while it is present in all rows of the current interval. Dense blocks shrink slowly, but then the number of rows/columns is bounded by the total number of points in the block. Sparse blocks die quickly. This is the exact “pay for surviving intersections” geometry trick: no magic, just making the obvious rectangle condition computable.

For each row interval with height at least $1$ and at least two common columns, compute the lengths of consecutive runs inside the sorted common-column vector and add $2L(L-1)$.

Finally:

1. Add all horizontal ordered pairs from row runs.
2. Add all vertical ordered pairs from column runs.
3. Add all positive-area rectangle corner pairs from consecutive-row blocks.

All counts fit in long long: the answer is at most $n(n-1)$ ordered pairs.

Algorithm summary

For each test case:

1. Read all points.
2. Group by row and sort columns.
3. Group by column and sort rows.
4. Count horizontal consecutive runs.
5. Count vertical consecutive runs.
6. Sort rows by $y$, split them into maximal blocks where adjacent row numbers differ by $1$.
7. For each block, enumerate row intervals, maintain the common sorted columns by intersection, and add consecutive-column run contributions.

The implementation uses only sorting, hash maps for grouping, and linear sorted-vector intersections. Pretty clean for a 2800. The statement looks scary; the rectangle observation is the whole boss fight.