You are given a set of N distinct points P_{1}, P_{2}, P_{3}, \ldots, P_{N} on a 2-D plane.

A triplet (i, j, k) is called a holy triplet if
1 ≤ i < j < k ≤ N
P_{i}, P_{j} and P_{k} are non-collinear and
Any two of the points P_{i}, P_{j} and P_{k} are [antipodal] points of the circle that passes through all three of them.

Two points on a circle are said to be antipodal points of the circle if they are diametrically opposite to each other.

Find the total number of holy triplets.

------ Input Format ------ 

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N - the number of points.
- Each of the next N lines contains two space separated integers x_{i} and y_{i}, denoting the co-ordinates of i-th point P_{i}.

------ Output Format ------ 

For each test case output a single line denoting the number of holy triplets.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$3 ≤ N ≤ 2000$
- Sum of $N$ over all test cases does not exceed $2000$
$-10^{9} ≤ x_{i}, y_{i} ≤ 10^{9}$
- All points $P_{1}, P_{2}, \ldots, P_{N}$ in each test case are distinct.

----- Sample Input 1 ------ 
1
4
0 1
0 -1
1 0
-1 0
----- Sample Output 1 ------ 
4
----- explanation 1 ------ 
Test case 1: The holy triplets in this case are
$$
\begin{array}{|c|c|c|c|}
\hline
\textbf{Holy Triplet} & 1 ≤ i < j < k ≤ N & \textbf{Non collinear} & \textbf{Antipodal points} \\ 
\hline
(1, 2, 3) & \checkmark & \checkmark & 1 \text{ and } 2 \\
\hline
(1, 2, 4) & \checkmark & \checkmark & 1 \text{ and } 2 \\
\hline
(1, 3, 4) & \checkmark & \checkmark & 3 \text{ and } 4  \\
\hline
(2, 3, 4) & \checkmark & \checkmark & 3 \text{ and } 4 \\
\hline
\end{array}
$$

Source: codechef | Difficulty: VERY_HARD
Tags: Geometry

Data structures

Mathematics


Solutions:
import math, bisect, heapq, random, sys, itertools
sys.setrecursionlimit(2 * 10 ** 5)
input = sys.stdin.readline

def slope(x1, y1, x2, y2):
	if x2 - x1 == 0:
		return 'inf'
	return float(y2 - y1) / (x2 - x1)
t = int(input())
for i in range(t):
	n = int(input())
	x = []
	y = []
	c = 0
	for k in range(n):
		s = [int(j) for j in input().split()]
		x.append(s[0])
		y.append(s[1])
	for j in range(0, n):
		m = {}
		for k in range(0, n):
			if k == j:
				continue
			if slope(x[j], y[j], x[k], y[k]) in m:
				m[slope(x[j], y[j], x[k], y[k])] += 1
				continue
			m[slope(x[j], y[j], x[k], y[k])] = 1
		for k in m:
			if k == 'inf':
				if 0 in m:
					c += m[0] * m[k]
				continue
			if k == 0:
				if 'inf' in m:
					c += m['inf'] * m[k]
				continue
			if 1 / k * -1 in m:
				c += m[1 / k * -1] * m[k]
	print(c // 2)


T = int(input())
for _ in range(T):
	N = int(input())
	c = []
	for _ in range(N):
		lis = [int(x) for x in input().split(' ')]
		c.append(lis)
	count = 0
	dic = {}
	for i in range(N - 1):
		for j in range(i, N):
			if i != j:
				(x1, y1) = c[i]
				(x2, y2) = c[j]
				if x1 == x2:
					if (0, i) in dic:
						count += dic[0, i]
					if (0, j) in dic:
						count += dic[0, j]
					if ('inf', i) in dic:
						dic['inf', i] += 1
					else:
						dic['inf', i] = 1
					if ('inf', j) in dic:
						dic['inf', j] += 1
					else:
						dic['inf', j] = 1
				else:
					m = (y2 - y1) / (x2 - x1)
					if m == 0:
						if ('inf', i) in dic:
							count += dic['inf', i]
						if ('inf', j) in dic:
							count += dic['inf', j]
					else:
						if (-1 / m, i) in dic:
							count += dic[-1 / m, i]
						if (-1 / m, j) in dic:
							count += dic[-1 / m, j]
					if (m, i) in dic:
						dic[m, i] += 1
					else:
						dic[m, i] = 1
					if (m, j) in dic:
						dic[m, j] += 1
					else:
						dic[m, j] = 1
	print(count)


import math
t = int(input())
for i in range(t):
	n = int(input())
	l = []
	for j in range(n):
		rows = list(map(int, input().split(' ')))
		l.append(rows)
	ans = 0
	for j in range(n):
		zero = 0
		inf = 0
		po = 0
		mo = 0
		ht1 = {}
		ht2 = {}
		for k in range(n):
			if k == j:
				continue
			x = l[k][0] - l[j][0]
			y = l[k][1] - l[j][1]
			if x != 0 and y != 0:
				m = y / x
			else:
				if x == 0:
					inf += 1
				if y == 0:
					zero += 1
				continue
			if m == 1:
				po += 1
			if m == -1:
				mo += 1
			if abs(m) < 1:
				if m in ht1:
					ht1[m] += 1
				else:
					ht1[m] = 1
			elif m != 1:
				if m in ht2:
					ht2[1 / m] += 1
				else:
					ht2[1 / m] = 1
		ll = list(ht1.keys())
		for k in range(len(ll)):
			if -ll[k] in ht2:
				ans += ht1[ll[k]] * ht2[-ll[k]]
		ans += zero * inf + po * mo
	print(ans)


from collections import defaultdict as dd
from math import gcd

def hasOppSign(a, b):
	return a > 0 and b < 0 or (a < 0 and b > 0)

def getPairSlope(x1, y1):
	if x1 < 0:
		return (y1, abs(x1))
	return (-y1, x1)

def countTangentSlopes(slopes):
	done = dd(bool)
	totalTangentPairs = 0
	for (m1, f1) in slopes.items():
		if m1 in done:
			continue
		m2 = getPairSlope(*m1)
		if m2 in slopes:
			totalTangentPairs += f1 * slopes[m2]
			done[m1] = True
			done[m2] = True
	return totalTangentPairs

def getSlope(Points, i, j):
	(x1, y1) = Points[i]
	(x2, y2) = Points[j]
	num = y2 - y1
	den = x2 - x1
	if den == 0:
		return (1, 0)
	mul = 1
	if hasOppSign(num, den):
		mul = -1
	(num, den) = (abs(num), abs(den))
	d = gcd(num, den)
	(num, den) = (num // d, den // d)
	return (mul * num, den)

def solve(Points, N):
	holyTriplets = 0
	for i in range(N - 2):
		slopes = dd(int)
		for ind in range(i + 1, N):
			slopes[getSlope(Points, i, ind)] += 1
		holyTriplets += countTangentSlopes(slopes)
	for j in range(1, N - 1):
		slopes = dd(int)
		for i in range(j):
			slopes[getSlope(Points, i, j)] += 1
		for k in range(j + 1, N):
			m2 = getSlope(Points, j, k)
			m1 = getPairSlope(*m2)
			holyTriplets += slopes[m1]
	for k in range(2, N):
		slopes = dd(int)
		for ind in range(k):
			slopes[getSlope(Points, k, ind)] += 1
		holyTriplets += countTangentSlopes(slopes)
	return holyTriplets
for case in range(int(input())):
	N = int(input())
	Points = []
	for i in range(N):
		Points.append(list(map(int, input().split())))
	print(solve(Points, N))


from collections import defaultdict
from math import trunc
for _ in range(int(input())):
	n = int(input())
	arr = []
	for _ in range(n):
		(a, b) = map(int, input().split())
		arr.append([a, b])

	def slope(a, b):
		if arr[a][0] == arr[b][0]:
			return 'c' if arr[a][1] > arr[b][1] else 'd'
		return (arr[b][1] - arr[a][1]) / (arr[b][0] - arr[a][0])
	ans = 0
	for i in range(n):
		temp = defaultdict(int)
		for j in range(n):
			if i != j:
				s = slope(i, j)
				temp[s] += 1
		for v in list(temp.keys()):
			if v != 0 and v != 'c' and (v != 'd') and (-1 / v in temp):
				ans += temp[-1 / v] * temp[v]
			elif v == 'c':
				ans += temp['c'] * temp[0]
			elif v == 'd':
				ans += temp['d'] * temp[0]
			elif v == 0:
				ans += temp['d'] * temp[0] + temp['c'] * temp[0]
	print(ans // 2)


t = int(input())
for _ in range(t):
	n = int(input())
	p = []
	for _ in range(n):
		p.append(tuple(map(int, input().split())))
	ans = 0
	for i in range(n):
		d = {}
		for j in range(n):
			if j == i:
				continue
			if p[i][0] - p[j][0] != 0:
				m = (p[i][1] - p[j][1]) / (p[i][0] - p[j][0])
			else:
				m = 10000000000.0
			if m not in d:
				d[m] = 0
			d[m] += 1
			if m == 0:
				m = 10000000000.0
			elif m == 10000000000.0:
				m = 0
			else:
				m = -1 / m
			if m in d:
				ans += d[m]
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	l = list()
	for i in range(n):
		(x, y) = map(int, input().split())
		l.append([x, y])
	ans = 0
	for i in range(n):
		d = dict()
		for j in range(n):
			if i != j:
				temp1 = l[i][0] - l[j][0]
				temp2 = l[i][1] - l[j][1]
				a1 = 0
				a2 = 0
				if temp1 == 0:
					a1 = 90
					if temp2 < 0:
						a1 = -90
					a2 = 0
				elif temp2 == 0:
					a1 = 0
					a2 = -90
					if temp1 < 0:
						a2 = 90
				else:
					a1 = math.atan(temp2 / temp1) * (180 / 3.14159265)
					a2 = math.atan(-temp1 / temp2) * (180 / 3.14159265)
				if a1 not in d.keys():
					d[a1] = 1
				else:
					d[a1] += 1
				if a2 in d.keys():
					ans += d[a2]
	print(ans)


t = int(input())

def slope(y1, y2, x1, x2):
	if x2 - x1 == 0:
		return 'inf'
	return (y2 - y1) / (x2 - x1)
for _ in range(t):
	res = 0
	n = int(input())
	(x, y) = ([], [])
	for _ in range(n):
		(a, b) = map(int, input().split())
		x.append(a)
		y.append(b)
	for i in range(n):
		m = {}
		for j in range(n):
			if i == j:
				continue
			if slope(y[i], y[j], x[i], x[j]) in m:
				m[slope(y[i], y[j], x[i], x[j])] += 1
				continue
			m[slope(y[i], y[j], x[i], x[j])] = 1
		for k in m:
			if k == 'inf':
				if 0.0 in m:
					res += m[0.0] * m[k]
				continue
			if k == 0.0:
				if 'inf' in m:
					res += m['inf'] * m[k]
				continue
			if 1 / k * -1 in m:
				res += m[1 / k * -1] * m[k]
	print(res // 2)


def slope(x1, y1, x2, y2):
	if x2 - x1 == 0:
		return 'inf'
	return float(y2 - y1) / (x2 - x1)
t = int(input())
for i in range(t):
	n = int(input())
	x = []
	y = []
	c = 0
	for k in range(n):
		s = [int(j) for j in input().split()]
		x.append(s[0])
		y.append(s[1])
	for j in range(0, n):
		m = {}
		for k in range(0, n):
			if k == j:
				continue
			if slope(x[j], y[j], x[k], y[k]) in m:
				m[slope(x[j], y[j], x[k], y[k])] += 1
				continue
			m[slope(x[j], y[j], x[k], y[k])] = 1
		for k in m:
			if k == 'inf':
				if 0 in m:
					c += m[0] * m[k]
				continue
			if k == 0:
				if 'inf' in m:
					c += m['inf'] * m[k]
				continue
			if 1 / k * -1 in m:
				c += m[1 / k * -1] * m[k]
	print(c // 2)


import sys
import math
from collections import defaultdict, Counter, deque
from bisect import *
from string import ascii_lowercase
from heapq import *

def readInts():
	x = list(map(int, sys.stdin.readline().rstrip().split()))
	return x[0] if len(x) == 1 else x

def readList(type=int):
	x = sys.stdin.readline()
	x = list(map(type, x.rstrip('\n\r').split()))
	return x

def readStr():
	x = sys.stdin.readline().rstrip('\r\n')
	return x
write = sys.stdout.write
read = sys.stdin.readline

def dist(x1, x2, y1, y2):
	return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

def mergeSort(arr, check=lambda a, b: a < b, reverse=False):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		mergeSort(L, check, reverse)
		mergeSort(R, check, reverse)
		i = j = k = 0
		while i < len(L) and j < len(R):
			if check(L[i], R[j]):
				if not reverse:
					arr[k] = L[i]
					i += 1
				else:
					arr[k] = R[j]
					j += 1
			elif not reverse:
				arr[k] = R[j]
				j += 1
			else:
				arr[k] = L[i]
				i += 1
			k += 1
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1

def maxSum(arr):
	max_sum = float('-inf')
	max_cur = 0
	for num in ar:
		max_cur = max(max_cur + num, num)
		if max_cur > max_sum:
			max_sum = max_cur
	return max_sum

def hcf(a, b):
	if b == 0:
		return a
	else:
		return hcf(b, b % a)

def get_power(n, m):
	i = 1
	p = -1
	while i <= n:
		i = i * m
		p += 1
	return p

def fact(n):
	f = 1
	for i in range(2, n + 1):
		f *= i
	return f

def find_closest(num, ar):
	min_d = float('inf')
	for num2 in ar:
		d = abs(num2 - num)
		if d < min_d:
			min_d = d
	return min_d

def solve(t):
	n = readInts()
	ar = []
	for _ in range(n):
		ar.append(list(readInts()))
	res = 0
	for i in range(n):
		x1 = ar[i][0]
		y1 = ar[i][1]
		m = {}
		for j in range(n):
			if i != j:
				x2 = ar[j][0]
				y2 = ar[j][1]
				tmp = 0
				if x1 != x2:
					tmp = (y2 - y1) / (x2 - x1)
					if tmp == -0:
						tmp = 0
				else:
					tmp = float('inf')
				req = 0
				if tmp == float('inf'):
					req = 0
				elif tmp == 0:
					req = float('inf')
				else:
					req = -(x2 - x1) / (y2 - y1)
				if req in m:
					res += m[req]
				if tmp in m:
					m[tmp] += 1
				else:
					m[tmp] = 1
		m.clear()
	print(res)

def main():
	t = 1
	sys.setrecursionlimit(12000)
	t = readInts()
	for i in range(t):
		solve(i + 1)
main()


def slope(a1, a2, b1, b2):
	if a1 - b1 == 0:
		return 'inf'
	return float(a2 - b2) / (a1 - b1)
for n in range(int(input())):
	k = int(input())
	li = []
	for i in range(k):
		li.append(list(map(int, input().split())))
	ans = 0
	sl = []
	for i in range(k):
		dici = {}
		for j in range(k):
			if i == j:
				continue
			if slope(li[i][0], li[i][1], li[j][0], li[j][1]) in dici:
				dici[slope(li[i][0], li[i][1], li[j][0], li[j][1])] += 1
			else:
				dici[slope(li[i][0], li[i][1], li[j][0], li[j][1])] = 1
		for i in dici.keys():
			if i == 'inf':
				if 0 in dici:
					ans += dici[i] * dici[0]
			elif i == 0:
				if 'inf' in dici:
					ans += dici[i] * dici['inf']
			elif -1 / i in dici:
				ans += dici[-1 / i] * dici[i]
	print(ans // 2)


from sys import stdin
input = stdin.readline

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def answer():
	ans = 0
	for i in range(n):
		d = dict()
		for j in range(n):
			if i == j:
				continue
			(x1, x2) = (coor[i][0], coor[j][0])
			(y1, y2) = (coor[i][1], coor[j][1])
			g = gcd(x1 - x2, y1 - y2)
			(num, den) = ((x1 - x2) // g, (y1 - y2) // g)
			ans += d.get((-num, den), 0)
			ans += d.get((num, -den), 0)
			d[den, num] = d.get((den, num), 0) + 1
	return ans
for T in range(int(input())):
	n = int(input())
	coor = []
	for i in range(n):
		(x, y) = map(int, input().split())
		coor.append([x, y])
	print(answer())


for _ in range(int(input())):
	n = int(input())
	points = []
	for i in range(n):
		(x, y) = map(int, input().split())
		points.append([x, y])
	dit = {}
	ans = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			if points[i] != points[j]:
				(x1, y1) = points[i]
				(x2, y2) = points[j]
				if x1 == x2:
					if (0, i) in dit:
						ans += dit[0, i]
					if (0, j) in dit:
						ans += dit[0, j]
					if ('inf', i) in dit:
						dit['inf', i] += 1
					else:
						dit['inf', i] = 1
					if ('inf', j) in dit:
						dit['inf', j] += 1
					else:
						dit['inf', j] = 1
				else:
					m = (y2 - y1) / (x2 - x1)
					if m == 0:
						if ('inf', i) in dit:
							ans += dit['inf', i]
						if ('inf', j) in dit:
							ans += dit['inf', j]
					else:
						if (-1 / m, i) in dit:
							ans += dit[-1 / m, i]
						if (-1 / m, j) in dit:
							ans += dit[-1 / m, j]
					if (m, i) in dit:
						dit[m, i] += 1
					else:
						dit[m, i] = 1
					if (m, j) in dit:
						dit[m, j] += 1
					else:
						dit[m, j] = 1
	print(ans)


from math import inf
t = int(input())
for _ in range(t):
	n = int(input())
	a = [0] * n
	for i in range(n):
		(x, y) = map(int, input().split())
		a[i] = (x, y)
	memo1 = [0] * n
	for (i, (x1, y1)) in enumerate(a):
		memo1[i] = {}
		for (x2, y2) in a:
			if x1 == x2 and y1 == y2:
				continue
			if not x2 - x1:
				slope = inf
			else:
				slope = (y2 - y1) / (x2 - x1)
			memo1[i][slope] = memo1[i].get(slope, 0) + 1
	memo2 = [0] * n
	for (i, (x1, y1)) in enumerate(a):
		memo2[i] = {}
		for (x2, y2) in a:
			if x1 == x2 and y1 == y2:
				continue
			if not y2 - y1:
				slope = inf
			else:
				slope = (x1 - x2) / (y2 - y1)
			memo2[i][slope] = memo2[i].get(slope, 0) + 1
	sumi = 0
	for (dt1, dt2) in zip(memo1, memo2):
		for slope in dt1:
			sumi += dt1[slope] * dt2.get(slope, 0)
	print(sumi // 2)


from math import gcd
t = int(input())
for _ in range(t):
	n = int(input())
	xs = []
	ys = []
	for _ in range(n):
		(x, y) = map(int, input().split())
		xs.append(x)
		ys.append(y)
	tot = 0
	for i in range(n):
		d = dict()
		posr = set()
		zs = 0
		infs = 0
		for j in range(n):
			if i == j:
				continue
			dx = xs[j] - xs[i]
			dy = ys[j] - ys[i]
			if dx == 0:
				infs += 1
			elif dy == 0:
				zs += 1
			else:
				g = gcd(dx, dy)
				dx //= g
				dy //= g
				if dy < 0:
					dx = -dx
					dy = -dy
				k = (dx, dy)
				if dx > 0:
					posr.add(k)
				if k not in d.keys():
					d[k] = 0
				d[k] += 1
		tot += zs * infs
		for k in posr:
			np = (-k[1], k[0])
			if np in d.keys():
				tot += d[k] * d[np]
	print(tot)


from collections import defaultdict
from math import gcd
from sys import stdin
input = stdin.readline
for test in range(int(input())):
	n = int(input())
	points = []
	for i in range(n):
		points.append(list(map(int, input().split())))
	slopes = [defaultdict(int) for i in range(n)]
	for i in range(n):
		for j in range(i + 1, n):
			p1 = points[i]
			p2 = points[j]
			dx = p1[0] - p2[0]
			dy = p1[1] - p2[1]
			sign = 1
			if dx * dy < 0:
				sign = -1
			dx = abs(dx)
			dy = abs(dy)
			g = gcd(dx, dy)
			dx //= g
			dy //= g
			slope = (sign * dy, dx)
			if slope[1] == 0:
				slope = (1, 0)
			elif slope[0] == 0:
				slope = (0, 1)
			slopes[i][slope] += 1
			slopes[j][slope] += 1
	ans = 0
	for i in range(n):
		for item in slopes[i]:
			slope = item
			wanted = (-slope[1], slope[0])
			sign = 1
			if wanted[0] * wanted[1] < 0:
				sign = -1
			wanted = (sign * abs(wanted[0]), abs(wanted[1]))
			if slope[0] == 0:
				wanted = (1, 0)
			elif slope[1] == 0:
				wanted = (0, 1)
			if wanted in slopes[i]:
				ans += slopes[i][slope] * slopes[i][wanted]
	print(ans // 2)


import math
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = []
	for i in range(0, n):
		(x, y) = input().split()
		x = int(x)
		y = int(y)
		a.append([x, y])
	dist = []
	c = 0
	for i in range(0, n):
		(x, y) = (a[i][0], a[i][1])
		has = {}
		for j in range(0, n):
			(x1, y1) = (a[j][0], a[j][1])
			if x1 == x and y1 == y:
				continue
			p = x1 - x
			q = y1 - y
			r = math.gcd(abs(p), abs(q))
			p /= r
			q /= r
			if (q, -p) in has.keys():
				c += has[q, -p]
			if (-q, p) in has.keys():
				c += has[-q, p]
			if (p, q) in has.keys():
				has[p, q] += 1
			else:
				has[p, q] = 1
	print(c)


from math import atan2, degrees
from bisect import bisect_left, bisect_right
T = int(input())
for _ in range(T):
	N = int(input())
	P = []
	for i in range(N):
		(x, y) = list(map(int, input().split()))
		P.append((x, y))
	answer = 0
	for k in range(N):
		deg = []
		for i in range(N):
			if i != k:
				y = P[i][1] - P[k][1]
				x = P[i][0] - P[k][0]
				deg.append(degrees(atan2(y, x)))
		deg.sort()
		min_deg = deg[0]
		new_deg = []
		for d in deg:
			new_deg.append(d - min_deg)
		deg = new_deg
		for angle in deg:
			val_1 = angle + 90.0
			j = bisect_left(deg, val_1)
			k = bisect_right(deg, val_1)
			answer += k - j
			val_2 = angle + 270.0
			j = bisect_left(deg, val_2)
			k = bisect_right(deg, val_2)
			answer += k - j
	print(answer)


def getSlope(x1, y1, x2, y2):
	if x1 == x2:
		return 'INF'
	return (y2 - y1) / (x2 - x1)

def invSlope(slope):
	if not slope:
		return 'INF'
	if slope == 'INF':
		return 0
	return -1 / slope
T = int(input())
for t in range(T):
	N = int(input())
	P = []
	ans = 0
	for i in range(N):
		P.append(list(map(int, input().split())))
	A = [{} for _ in range(N)]
	for i in range(N):
		for j in range(i + 1, N):
			slopeVal = getSlope(P[i][0], P[i][1], P[j][0], P[j][1])
			count = A[i].get(invSlope(slopeVal), 0) + A[j].get(invSlope(slopeVal), 0)
			if count:
				ans += count
			A[i][slopeVal] = A[i].get(slopeVal, 0) + 1
			A[j][slopeVal] = A[j].get(slopeVal, 0) + 1
	print(ans)


from collections import defaultdict
from math import gcd
for tcase in range(int(input())):
	n = int(input())
	(x, y) = ([0] * n, [0] * n)
	for i in range(n):
		(x[i], y[i]) = map(int, input().split())
	ans = 0
	for i in range(n):
		points = defaultdict(int)
		for j in range(n):
			if j != i:
				dx = x[j] - x[i]
				dy = y[j] - y[i]
				g = gcd(dx, dy)
				dx //= g
				dy //= g
				points[dx, dy] += 1
		for (dx, dy) in points.keys():
			if (-dy, dx) in points:
				ans += points[dx, dy] * points[-dy, dx]
	print(ans)


T = int(input())
for t in range(T):
	N = int(input())
	X = [-1] * N
	Y = [-1] * N
	for i in range(N):
		(X[i], Y[i]) = map(int, input().split(' '))
	lines = dict()
	for i in range(N):
		for j in range(i + 1, N):
			if X[i] != X[j]:
				tg = (Y[i] - Y[j]) / (X[i] - X[j])
			else:
				tg = 'inf'
			if tg not in lines.keys():
				lines[tg] = dict()
			if (X[i], Y[i]) not in lines[tg].keys():
				lines[tg][X[i], Y[i]] = 1
			else:
				lines[tg][X[i], Y[i]] += 1
			if (X[j], Y[j]) not in lines[tg].keys():
				lines[tg][X[j], Y[j]] = 1
			else:
				lines[tg][X[j], Y[j]] += 1
	triplets = 0
	for key in lines.keys():
		if key == 'inf' and 0.0 in lines.keys():
			for dots in lines['inf']:
				if dots in lines[0.0]:
					triplets += 2 * lines['inf'][dots] * lines[0.0][dots]
		elif key != 'inf' and key != 0 and (-1 / key in lines.keys()):
			for dots in lines[key]:
				if dots in lines[-1 / key]:
					triplets += lines[key][dots] * lines[-1 / key][dots]
	print(triplets // 2)


from math import gcd
t = int(input())
for _ in range(t):
	n = int(input())
	pts = []
	for _ in range(n):
		(x, y) = map(int, input().split())
		pts.append((x, y))
	ans = 0
	for i in range(n):
		lk = {}
		count_y = 0
		count_x = 0
		for j in range(n):
			if i == j:
				continue
			cx = pts[j][0] - pts[i][0]
			cy = pts[j][1] - pts[i][1]
			d = gcd(cx, cy)
			cx = cx // d
			cy = cy // d
			if cx * cy > 0:
				cx = abs(cx)
				cy = abs(cy)
			elif cy < 0:
				cx = -cx
				cy = -cy
			if cx * cy == 0:
				if cx == 0:
					ans += count_y
					count_x += 1
				else:
					ans += count_x
					count_y += 1
				if (x, y) in lk:
					lk[x, y] += 1
				else:
					lk[x, y] = 1
			else:
				nx = -cy
				ny = cx
				if nx * ny > 0:
					nx = abs(nx)
					ny = abs(ny)
				elif ny < 0:
					nx = -nx
					ny = -ny
				if (nx, ny) in lk:
					ans += lk[nx, ny]
				if (cx, cy) in lk:
					lk[cx, cy] += 1
				else:
					lk[cx, cy] = 1
	print(ans)