The images are hosted on Github, use an accelerator if it fails to load.
Consider drawing the Huffman distance of three points.
Then we have a+b+c=a+b+d=c+d, i.e. a+b=c=d. This means that the slope of \overline{BC} is \pm1 and A is on a line parallel to it.
We might as well \mathcal{O}(n^2) enumerate B, \mathcal{O}(n) enumerate C, and compute the number of legal A by difference \mathcal{O}(1). Complexity \mathcal{O}(n^3) with large constants.
Specifically, we enumerate (i,j) and k<i, and the problem translates into finding the number of a_{x,y}=1 on the four lines. It is sufficient to preprocess the prefix sum for each line with slope \pm1.
Note that to avoid double counting
, it may be worthwhile to count the special endpoint positions separately.