Square Overlap

You are planning to build $N$ square fenced-in pastures, each of size exactly $K \times K$. Pasture $i$ is centered at the integer-coordinate point $(x_i, y_i)$. Because every pasture is an axis-aligned square, pasture $i$ covers the region $[x_i - K/2,\ x_i + K/2] \times [y_i - K/2,\ y_i + K/2]$.

While drafting the plans, you worry that two pastures may accidentally overlap, meaning the two squares share a region of positive area (merely touching along an edge or at a corner does not count). No two pastures share the same center point.

Given the center of every planned pasture, compute the area shared by the two overlapping pastures. Print $0$ if no two pastures overlap, and print $-1$ if more than one pair of pastures overlaps.

• The first line contains two space-separated integers $N$ and $K$ ($2 \le N \le 50{,}000$, $1 \le K \le 1{,}000{,}000$). $K$ is guaranteed to be even.
• Each of the next $N$ lines contains two integers $x_i$ and $y_i$ ($-1{,}000{,}000 \le x_i, y_i \le 1{,}000{,}000$), the center of pasture $i$.

• Print a single line containing the area shared by the two overlapping pastures. Print $0$ if no two pastures overlap, and print $-1$ if more than one pair of pastures overlaps.

Two pastures $i$ and $j$ overlap with positive area if and only if $|x_i - x_j| < K$ and $|y_i - y_j| < K$. When they do, their shared area equals $(K - |x_i - x_j|) \times (K - |y_i - y_j|)$.