Gregor and the Odd Cows (Easy) (Codeforces 1549F1)
Tags: Others, geometry

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: 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: 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.

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)$$$ 

Sample Inputs:
3
0 0
2 0
0 4

5
0 0
2 16
30 14
4 6
2 10

Sample Outputs:
1

3

Solution (Python):
n = int(input())
m = [0] * 4
for i in range(n):
    (a, b) = map(int, input().split())
    a %= 4
    b %= 4
    if a == 0 and b == 0:
        m[0] += 1
    elif a == 0 and b == 2:
        m[1] += 1
    elif a == 2 and b == 0:
        m[2] += 1
    else:
        m[3] += 1
ans = 0
for i in range(4):
    for j in range(4):
        if i == j:
            ans += m[i] * (m[i] - 1) * (m[i] - 2) // 6
        else:
            ans += m[i] * (m[i] - 1) // 2 * m[j]
print(ans)

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for i in range(1):
    n = int(input())
    bucket = [0] * 4
    pts = [tuple(map(int, input().split())) for i in range(n)]
    for (x, y) in pts:
        i = 0
        if x % 4:
            i += 1
        if y % 4:
            i += 2
        bucket[i] += 1
    ans = 0
    for i in bucket:
        ans += i * (i - 1) * (i - 2) // 6
        ans += (i - 1) * i // 2 * (n - i)
    print(ans)

Solution (Python):
from collections import Counter
from math import gcd
from sys import stdin, gettrace
if gettrace():

    def inputi():
        return input()
else:

    def input():
        return next(stdin)[:-1]

    def inputi():
        return stdin.buffer.readline()

def verticies_under(a, b):
    (x1, y1) = a
    (x2, y2) = b
    return abs((x2 - x1 - 1) * (y2 + y1 - 1) - gcd(x2 - x1, y2 - y1)) // 2

def main():
    n = int(input())
    posts = [tuple((int(a) % 4 for a in input().split())) for _ in range(n)]
    pc = Counter(posts)
    res = n * (n - 1) * (n - 2) // 6 - (pc[0, 0] + pc[2, 2]) * pc[0, 2] * pc[2, 0] - (pc[0, 2] + pc[2, 0]) * pc[0, 0] * pc[2, 2]
    print(res)
if __name__ == '__main__':
    main()