Gregor and the Odd Cows (Hard)
Contest: Codeforces Round 736 (Div. 1)
Difficulty rating: 3300
Tags: brute force, geometry, math, number theory

This is the hard version of the problem. The only difference from the easy version is that in this version the coordinates can be both odd and even.

There are $$$n$$$ fence-posts at distinct coordinates on a plane. It is guaranteed that no three fence posts lie on the same line.

There are an infinite number of cows on the plane, one at every point with integer coordinates.

Gregor is a member of the Illuminati, and wants to build a triangular fence, connecting $$$3$$$ distinct existing fence posts. A cow strictly inside the fence is said to be enclosed. If there are an odd number of enclosed cows and the area of the fence is an integer, the fence is said to be interesting.

Find the number of interesting fences.

Input format:
The first line contains the integer $$$n$$$ ($$$3 \le n \le 6000$$$), the number of fence posts which Gregor can choose to form the vertices of a fence.

Each of the next $$$n$$$ line contains two integers $$$x$$$ and $$$y$$$ ($$$0 \le x,y \le 10^7$$$, where $$$(x,y)$$$ is the coordinate of a fence post. All fence posts lie at distinct coordinates. No three fence posts are on the same line.

Output format:
Print a single integer, the number of interesting fences. Two fences are considered different if they are constructed with a different set of three fence posts.

Constraints:
Time limit: 6.0 s
Memory limit: 256.0 MB

Note:
In the first example, there is only $$$1$$$ fence. That fence is interesting since its area is $$$4$$$ and there is $$$1$$$ enclosed cow, marked in red.

In the second example, there are $$$4$$$ possible fences. Only one of them is interesting however. That fence has an area of $$$8$$$ and $$$5$$$ enclosed cows.

Example input:
3
0 0
2 0
0 4

Example output:
1

Example input:
4
1 8
0 6
5 2
5 6

Example output:
1

Editorial:
We want to find the number of lattice triangles formed by the fenceposts that have an odd number of interior points and an integral area. By Pick's Theorem, $$$area=I+\frac{B}{2}-1$$$, so $$$2\cdot area=2I+B-2$$$.
Let $$$A=2\cdot area$$$, so $$$A=2I+B-2$$$. Since $$$I$$$ is odd, taking both sides modulo 4 we get that $$$A \equiv B\mod{4}$$$, with the additional constraint that $$$A$$$ is even.
• Definition: The $$$\textbf{modularity}$$$ of a point $$$(x,y)$$$ is $$$(x\%4,y\%4)$$$.
• Definition: The $$$\textbf{boundary count}$$$ of a segment is the number of lattice points on that segment, minus 1.
Let's precompute the array $$$cnt[i][x][y][b]$$$ (dimensions $$$N\times 4\times 4\times 4$$$), which equals the number of other points with modularity $$$(x,y)$$$ and with a boundary count mod 4 equal to $$$b$$$. This precomputation can be done in $$$\mathcal{O}(N^2 \log{10^9})$$$ time, by iterating over every pair of points. The number of boundary points connected to the segment $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ is $$$\gcd{(|x_2-x_1|,|y_2-y_1|)}$$$.
Consider the number of boundary points on the three sides of a triangle, and call them $$$b_1,b_2,b_3$$$. Clearly, $$$B=b_1+b_2+b_3$$$. The key idea is that since $$$B$$$ is even, wlog we can assume that $$$b_3$$$ is even, and that $$$b_1 \equiv b_2 \mod{2}$$$. The other key idea is that it is easy to figure out if the boundary count is congruent to 0 or 2 mod 4, but it's hard if the boundary count is odd.
Let's fix a point, and count the number of triangles that involve this point. Let's also iterate over all the relevant modularities of the other two points in the triangle, which range from $$$(0,0)$$$ up to $$$(3,3)$$$. Let's also make sure that there are an even number of boundary points on the side opposite the fixed point, which we know almost nothing about. It can be shown that $$$b_3 \equiv 0\mod{4}$$$ IFF $$$(x_1,y_1)=(x_2,y_2)$$$, and that $$$b_3 \equiv 2\mod{4}$$$ IFF $$$x_1,x_2$$$ have the same parity, and $$$y_1,y_2$$$ have the same parity, and the previous case doesn't apply. Finally, make sure that the parity of the boundary count of the two sides next to the fixed point are the same.
Using the precomputed array $$$cnt$$$ and the formula for $$$b_3$$$, we can quickly find $$$B$$$ in this case. Using the Shoelace Formula, we can quickly find what $$$A$$$ is modulo 4. If $$$A$$$ is even and equal to $$$B$$$, then we know that $$$I$$$ must be odd, so all triangles in this class are "interesting". Thus, we add to the answer a number roughly equal to $$$cnt[i][x_1][y_1][b_1]\cdot cnt[i][x_2][y_2][b_2]$$$ (it could be lower due to the potential overcount).
Lastly, be sure not to overcount triangles! In my code, I count each of the "EEE" triangles ($$$b_1,b_2,b_3$$$ all even) 3 times, and the "OOE" triangles once.
Time Complexity: $$$\mathcal{O}(N^2 \log{10^9})$$$ (the main part of the solution is approximately $$$\mathcal{O}(512N)$$$.