Triangles

Observation 1: make triangles behave nicely

A triangle is much easier to analyze if its vertices are ordered by increasing $x$-coordinate: $r_i, r_k, r_j \quad \text{with} \quad x_i < x_k < x_j.$ Then the triangle is $x$-monotone: every vertical line intersects it in either nothing or one segment. That’s exactly the kind of geometry we can count with.

There’s one stupid little issue: some points may share the same $x$-coordinate. We kill that deterministically with a shear transform:

$$(x, y) \mapsto (x', y') = (Cx + y, y),$$

where $C > 2 \cdot 10^9$, for example $C = 4000000001$.

Why this works:

• It is a linear transform with positive determinant, so it preserves orientation, collinearity, inside/outside — all the geometry we care about.
• All new $x'$-coordinates are distinct. If two points were different and had the same $x'$, then $C(x_1-x_2) = y_2-y_1,$ impossible because the left side has magnitude at least $C > 2\cdot 10^9$, while the right side has magnitude at most $2\cdot 10^9$.

So from now on, assume every point has a unique $x$.

Observation 2: define a pairwise blue-count

Sort the red points by increasing $x$. For every pair $i < j$, define

$$f[i][j] = \#\{b \in \text{blue} : x_i < x_b < x_j \text{ and } b \text{ lies below the directed line } r_i \to r_j\}.$$

Formally, “below” means

$$\operatorname{cross}(r_j-r_i,\ b-r_i) < 0.$$

Because no three points are collinear, we never have to deal with a blue point sitting exactly on an edge. Thank God.

Observation 3: the key identity for one triangle

Take any red triangle, and write its vertices in $x$-order as $i < k < j$. Look at

$$g = f[i][k] + f[k][j] - f[i][j].$$

This is the whole problem hiding in one line.

Case 1: $r_k$ is above segment $r_i r_j$

Then the broken chain $r_i \to r_k \to r_j$ is the upper boundary of the triangle, and $r_i \to r_j$ is the base.

For a blue point with $x \in (x_i, x_k)$, the contribution to $g$ is

$$[\text{below } ik] - [\text{below } ij].$$

That is:

• $1$ iff the point lies between the lines $ik$ and $ij$,
• $0$ otherwise.

But on that $x$-interval, “between those two lines” is exactly “inside the triangle”. The same argument works on $(x_k, x_j)$ using lines $kj$ and $ij$.

So in this case,

$$g = \#(\text{blue points inside } \triangle i k j).$$

Case 2: $r_k$ is below segment $r_i r_j$

Now the chain $r_i \to r_k \to r_j$ is the lower boundary of the triangle. The exact same slice argument shows every blue point inside contributes $-1$, and every blue point outside contributes $0$. So

$$g = -\#(\text{blue points inside } \triangle i k j).$$

Conclusion

In both cases,

$$\triangle i k j \text{ contains no blue point inside } \iff g = 0.$$

So the emptiness condition becomes the gloriously simple

$$f[i][k] + f[k][j] = f[i][j].$$

That’s the aha. Everything else is bookkeeping.

Algorithm

1. Apply the shear transform to all points.
2. Sort red points by transformed $x$.
3. Precompute $f[i][j]$ for all $i<j$:
   • loop over all blue points,
   • check whether its $x$ lies strictly between $x_i$ and $x_j$,
   • check whether it is below segment $r_i r_j$.
4. Enumerate all triples $i<k<j$ of red points.
5. Count those satisfying $f[i][k] + f[k][j] = f[i][j].$

Each triangle is counted exactly once because after the shear, the three red vertices have distinct $x$-coordinates, hence a unique order $i<k<j$.

Correctness sketch

We proved the central lemma:

$$f[i][k] + f[k][j] - f[i][j] = \begin{cases} \#\text{inside blue points}, & r_k \text{ above } r_i r_j, \\ -\#\text{inside blue points}, & r_k \text{ below } r_i r_j. \end{cases}$$

Therefore the expression is zero iff the triangle contains no blue point inside.

Since every red triangle has a unique left-middle-right order after the shear, counting all triples $i<k<j$ satisfying the equality counts exactly all valid triangles.

Done. Neat, sharp, and not even that much code. Geometry problems occasionally decide not to be assholes.

Complexity

Precomputing all $f[i][j]$ takes $O(N^2 M).$ Counting all triples takes $O(N^3).$ So total complexity is $O(N^2M + N^3) = O(N^2(N+M)).$

With $N, M \le 500$, this is easily fine.

Memory usage is $O(N^2).$