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.


-----Examples-----

Input
3
0 0
2 0
0 4
Output
1
Input
5
0 0
2 16
30 14
4 6
2 10
Output
3


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

Difficulty: HARD
Tags: Geometry

Number theory

Bit manipulation

Mathematics
Skill types: Bit manipulation

Starter code:

Solutions:
from collections import defaultdict

def c2(x):
	return x * (x - 1) // 2

def c3(x):
	return x * (x - 1) * (x - 2) // 6
while True:
	try:
		counts = defaultdict(int)
		n = int(input().strip())
		for _ in range(n):
			(x, y) = map(int, input().strip().split())
			counts[x % 4, y % 4] += 1
		ans = c3(counts[0, 0]) + c3(counts[0, 2]) + c3(counts[2, 0]) + c3(counts[2, 2])
		ans += c2(counts[0, 0]) * (n - counts[0, 0]) + c2(counts[0, 2]) * (n - counts[0, 2]) + c2(counts[2, 0]) * (n - counts[2, 0]) + c2(counts[2, 2]) * (n - counts[2, 2])
		print(ans)
	except EOFError:
		break


n = int(input())
num = [0, 0, 0, 0]
for _ in range(n):
	(x, y) = map(int, input().split())
	num[bool(x & 2) + (y & 2)] += 1
print(n * (n - 1) * (n - 2) // 6 - num[0] * num[1] * num[2] - num[0] * num[1] * num[3] - num[0] * num[2] * num[3] - num[1] * num[2] * num[3])


from math import gcd
M = 4
n = int(input())
cnt = [0] * M * M
for i in range(n):
	(x, y) = map(int, input().split())
	cnt[x % M * M + y % M] += 1

def boundary(i, j):
	return gcd(i % M - j % M, i // M - j // M)
ans = 0
for i in range(M * M):
	for j in range(i, M * M):
		for k in range(j, M * M):
			if (boundary(i, j) + boundary(i, k) + boundary(j, k)) % 4 == 0:
				cur = cnt[i]
				cur = cur * cnt[j] if i != j else cur * (cnt[j] - 1) // 2
				cur = cur * cnt[k] if j != k else cur * (cnt[k] - 1) // 2 if k != i else cur * (cnt[k] - 2) // 3
				ans += cur
print(ans)


import math, sys
input = sys.stdin.readline
n = int(input())
p = [list(map(int, input().split())) for _ in range(n)]
ans = 0
cnt = 0
r = [[0] * n for _ in range(n)]
q = [0] * n
for i in range(n):
	for j in range(i + 1, n):
		if math.gcd(abs(p[i][0] - p[j][0]), abs(p[i][1] - p[j][1])) % 4 == 0:
			cnt += 1
			r[i][j] = 1
			q[i] += 1
			ans += n - 2
for i in range(n):
	for j in range(1, n):
		if r[i][j] == 1:
			ans -= q[j] * 2
print(ans)


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n, mod=0):
		self.BIT = [0] * (n + 1)
		self.num = n
		self.mod = mod

	def query(self, idx):
		res_sum = 0
		mod = self.mod
		while idx > 0:
			res_sum += self.BIT[idx]
			if mod:
				res_sum %= mod
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		mod = self.mod
		while idx <= self.num:
			self.BIT[idx] += x
			if mod:
				self.BIT[idx] %= mod
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		self.size = n
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		if r == self.size:
			r = self.num
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return -1
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.buffer.readline()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
n = int(input())
xy = [mi() for i in range(n)]
for i in range(n):
	(x, y) = xy[i]
	xy[i] = (x // 2, y // 2)
parity = [0 for i in range(4)]
for (x, y) in xy:
	p = 2 * (x & 1) + (y & 1)
	parity[p] += 1
res = 0
for i in range(n):
	for j in range(i + 1, n):
		(x0, y0) = xy[i]
		(x1, y1) = xy[j]
		if x0 - x1 & 1 == 0 and y0 - y1 & 1 == 0:
			t = 0
		else:
			t = 1
		for p in range(4):
			x2 = p >> 1 & 1
			y2 = p & 1
			tmp = t
			if x0 - x2 & 1 or y0 - y2 & 1:
				tmp += 1
			if x1 - x2 & 1 or y1 - y2 & 1:
				tmp += 1
			if tmp & 1 == 0:
				plus = parity[p]
				if 2 * (x0 & 1) + (y0 & 1) == p:
					plus -= 1
				if 2 * (x1 & 1) + (y1 & 1) == p:
					plus -= 1
				res += plus
print(res // 3)


import sys
input = lambda : sys.stdin.readline().rstrip()
N = int(input())
A = [0] * 4
for _ in range(N):
	(x, y) = map(int, input().split())
	(x, y) = (x // 2, y // 2)
	A[x % 2 * 2 + y % 2] += 1
ans = 0
for i in range(4):
	a = A[i]
	s = a * (a - 1) // 2
	ans += s * (a - 2) // 3
	for j in range(4):
		if i == j:
			continue
		b = A[j]
		ans += s * b
print(ans)


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.buffer.readline
	N = int(input())
	XY = []
	for _ in range(N):
		XY.append(tuple(map(int, input().split())))
	ans1 = ans2 = 0
	for i in range(N):
		cnt = [0] * 4
		(xi, yi) = XY[i]
		for j in range(N):
			if j == i:
				continue
			(xj, yj) = XY[j]
			if (xi - xj) % 4 == 0 and (yi - yj) % 4 == 0:
				cnt[0] += 1
			elif (xi - xj) % 4 == 2 and (yi - yj) % 4 == 0:
				cnt[1] += 1
			elif (xi - xj) % 4 == 0 and (yi - yj) % 4 == 2:
				cnt[2] += 1
			else:
				cnt[3] += 1
		ans1 += cnt[0] * (cnt[0] - 1) // 2
		ans2 += cnt[1] * (cnt[1] - 1) // 2
		ans2 += cnt[2] * (cnt[2] - 1) // 2
		ans2 += cnt[3] * (cnt[3] - 1) // 2
	assert ans1 % 3 == 0
	print(ans1 // 3 + ans2)
main()


n = int(input())
posts = [tuple(map(int, input().split())) for _ in range(n)]
buckets = [0] * 4
for (x, y) in posts:
	i = 0
	if x % 4:
		i += 1
	if y % 4:
		i += 2
	buckets[i] += 1
out = 0
for v in buckets:
	out += v * (v - 1) * (v - 2) // 6
	out += v * (v - 1) // 2 * (n - v)
print(out)


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)