Gregor and the Odd Cows (Easy)
Contest: Codeforces Round 736 (Div. 1)
Difficulty rating: 2300
Tags: bitmasks, geometry, math, number theory

This is the easy version of the problem. The only difference from the hard version is that in this version all coordinates are 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$$$, $$$x$$$ and $$$y$$$ are even), 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 $$$3$$$ interesting fences.

- $$$(0,0)$$$ — $$$(30,14)$$$ — $$$(2,10)$$$
- $$$(2,16)$$$ — $$$(30,14)$$$ — $$$(2,10)$$$
- $$$(30,14)$$$ — $$$(4,6)$$$ — $$$(2,10)$$$

Example input:
3
0 0
2 0
0 4

Example output:
1

Example input:
5
0 0
2 16
30 14
4 6
2 10

Example output:
3

Editorial:
We want to find the number of lattice triangles formed by the fenceposts that have an odd number of interior points (the area is automatically an even integer since all the coordinates are even). By Pick's Theorem, $$$area=I+\frac{B}{2}-1$$$, so $$$2\cdot area=2I+B-2$$$. $$$I$$$ is the number of interior points, and $$$B$$$ is the number of boundary points, for an arbitrary triangle formed by 3 fenceposts.
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}$$$. Since the area is an even integer, we get that $$$A\equiv B\equiv 0\mod{4}$$$.
Let's define the $$$\textbf{boundary count}$$$ of a segment to be the number of lattice points on it, minus 1. It can be proven that boundary count of the segment connecting $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ is $$$\gcd{(|x_2-x_1|,|y_2-y_1|)}$$$.
In this problem, we only care about what the boundary count is modulo 4. Since all the coordinates are even, the GCD is guaranteed to be even, so the boundary count is either 0 or 2 mod 4. For the segment connecting $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ call its boundary count $$$b$$$.
• $$$b\equiv 0\mod{4}$$$ IFF $$$x_1\equiv x_2 \mod{4}$$$ AND $$$y_1\equiv y_2 \mod{4}$$$.
• $$$b\equiv 2\mod{4}$$$ in all other situations.
Key Idea: Turn fence post $$$(x,y)$$$ into $$$(x\mod{4},y\mod{4})$$$.
The area mod 4 (what we care about) won't change if the coordinates are modded by 4. Additionally, by our work above, $$$B$$$ is entirely dependent on the coordinates mod 4.
Let $$$cnt[x][y]$$$ be a $$$4\times 4$$$ array counting the number points that fall into each category based on the key idea above. Since all coordinates are even, only 4 elements in the $$$cnt$$$ array will be nonzero. We can fix each point of the triangle into one of the categories and solve the problem. Be careful not to overcount triangles.
The time complexity is $$$\mathcal{O}(N)$$$, with a small constant for the counting.