Everyone knows what a square looks like. Mathematically, a square is a regular quadrilateral. This means that it has four equal sides and four equal angles (90 degree angles).
One beautiful day, Johnny eagerly examined the interesting properties of squares. He did not forget you, his best friend and a talented programmer and thus made a problem about squares to challenge your programming ability. The problem is: given a set of N points in the plane, how many squares are there such that all their corners belong to this set?
Now let's show Johnny your skill!

------ Input ------ 

The first line contains t, the number of test cases (about 10). Then t test cases follow.
Each test case has the following form:
The first line contains an integer N, the number of points in the given set (4 ≤ N ≤ 500).
Then N lines follow, each line contains two integers X, Y describing coordinates of a point (-50 ≤ X, Y ≤ 50).

------ Output ------ 

For each test case, print in a single line the number of squares that have vertices belong to the given set.

----- Sample Input 1 ------ 
1
7
0 0
0 1
1 0
1 1
1 2
2 1
2 2
----- Sample Output 1 ------ 
3
----- explanation 1 ------ 
The three squares are: (0 0), (0 1), (1 1), (1 0)(1 1), (1 2), (2 2), (2 1)(0 1), (1 0), (2 1), (1 2)

Difficulty: MEDIUM_HARD
Tags: Geometry

Mathematics

Complete search
Skill types: Complete search

Starter code:

Solutions:
def count_squares(x_coords, y_coords):
	point_set = set(zip(x_coords, y_coords))
	count = 0
	for i in range(len(x_coords)):
		for j in range(i + 1, len(x_coords)):
			dx = x_coords[j] - x_coords[i]
			dy = y_coords[j] - y_coords[i]
			if (x_coords[i] + dy, y_coords[i] - dx) in point_set and (x_coords[j] + dy, y_coords[j] - dx) in point_set:
				count += 1
			if (x_coords[i] - dy, y_coords[i] + dx) in point_set and (x_coords[j] - dy, y_coords[j] + dx) in point_set:
				count += 1
	return count // 4
I = int(input())
for i in range(I):
	N = int(input())
	X = []
	Y = []
	for i in range(N):
		input_string = input()
		input_list = input_string.split()
		x = int(input_list[0])
		y = int(input_list[1])
		X.append(x)
		Y.append(y)
	print(count_squares(X, Y))


def signature(x1, y1, x2, y2):
	if x1 > x2 or (x1 == x2 and y1 > y2):
		(x1, x2, y1, y2) = (x2, x1, y2, y1)
	(dx, dy) = (x2 - x1, y2 - y1)
	dot = dx * x1 + dy * y1
	return (x1, y1, x2, y2, dx, dy, dot)

def length(x1, y1, x2, y2):
	return (x1 - x2) ** 2 + (y1 - y2) ** 2

def squares(x, y):
	N = len(x)
	table = {}
	for i in range(N - 1):
		for j in range(i + 1, N):
			(x1, y1, x2, y2) = (x[i], y[i], x[j], y[j])
			(x1, y1, x2, y2, dx, dy, dot) = signature(x1, y1, x2, y2)
			if dx not in table:
				table[dx] = {}
			if dy not in table[dx]:
				table[dx][dy] = set()
			table[dx][dy].add((x1, y1, x2, y2))
	total = 0
	for i in range(N - 1):
		for j in range(i + 1, N):
			(x1, y1, x2, y2) = (x[i], y[i], x[j], y[j])
			(x1, y1, x2, y2, dx, dy, dot) = signature(x1, y1, x2, y2)
			(tx, ty) = (y1 - y2, x2 - x1)
			if (x1 + tx, y1 + ty, x2 + tx, y2 + ty) in table[dx][dy]:
				total += 1
			if (x1 - tx, y1 - ty, x2 - tx, y2 - ty) in table[dx][dy]:
				total += 1
	return total // 4

def rectangles(x, y):
	N = len(x)
	table = {}
	for i in range(N - 1):
		for j in range(i + 1, N):
			(x1, x2, y1, y2) = (x[i], x[j], y[i], y[j])
			(x1, x2, y1, y2, dx, dy, dot) = signature(x1, y1, x2, y2)
			if dx not in table:
				table[dx] = {}
			if dy not in table[dx]:
				table[dx][dy] = {}
			if dot not in table[dx][dy]:
				table[dx][dy][dot] = []
			table[dx][dy][dot].append((x1, y1, x2, y2))
	total = 0
	for dx in table.keys():
		for dy in table[dx].keys():
			for dot in table[dx][dy].keys():
				n = len(table[dx][dy][dot])
				total += n * (n - 1) / 2
	return total / 2
num_test = int(input())
for test in range(num_test):
	n = int(input())
	(x, y) = ([], [])
	for i in range(n):
		nums = input().split(' ')
		x.append(int(nums[0]))
		y.append(int(nums[1]))
	print(squares(x, y))


tc = int(input())
for tcn in range(tc):
	np = int(input())
	points = set()
	for i in range(np):
		l = input().strip().split()
		points.add((int(l[0]), int(l[1])))
	squares = 0
	for p1 in points:
		for p2 in points:
			if p1[0] != p2[0] or p1[1] != p2[1]:
				cx = (p1[0] + p2[0]) / 2.0
				cy = (p1[1] + p2[1]) / 2.0
				t1 = (p1[0] - cx, p1[1] - cy)
				t2 = (p2[0] - cx, p2[1] - cy)
				r1 = (t1[1], -t1[0])
				r2 = (t2[1], -t2[0])
				rt1 = (r1[0] + cx, r1[1] + cy)
				rt2 = (r2[0] + cx, r2[1] + cy)
				if rt1 in points and rt2 in points:
					squares += 1
	print(int(squares / 4))


def count_squares(points):
	squares = 0
	points_list = list(points)
	for p1 in points_list:
		for p2 in points_list:
			if p1 != p2:
				diff_vector = (p2[0] - p1[0], p2[1] - p1[1])
				rotated_vector = (p2[1] - p1[1], -p2[0] + p1[0])
				p3 = (p2[0] + rotated_vector[0], p2[1] + rotated_vector[1])
				p4 = (p1[0] + rotated_vector[0], p1[1] + rotated_vector[1])
				if p3 in points and p4 in points:
					squares += 1
	return squares // 4
num_tests = int(input())
for i in range(num_tests):
	N = int(input())
	points_set = set()
	for j in range(N):
		(num1, num2) = map(int, input().split())
		points_set.add((num1, num2))
	print(count_squares(points_set))


def count_squares(points):
	squares = 0
	squares_found = set()
	points_list = list(points)
	for (i, p1) in enumerate(points_list):
		for (j, p2) in enumerate(points_list[i + 1:]):
			diff_vector = (p2[0] - p1[0], p2[1] - p1[1])
			rotated_vector = (p2[1] - p1[1], -p2[0] + p1[0])
			p3 = (p2[0] + rotated_vector[0], p2[1] + rotated_vector[1])
			p4 = (p1[0] + rotated_vector[0], p1[1] + rotated_vector[1])
			square_as_tuple = tuple(sorted((p1, p2, p3, p4)))
			if p3 in points and p4 in points and (square_as_tuple not in squares_found):
				squares += 1
				squares_found.add(square_as_tuple)
			p3 = (p2[0] - rotated_vector[0], p2[1] - rotated_vector[1])
			p4 = (p1[0] - rotated_vector[0], p1[1] - rotated_vector[1])
			square_as_tuple = tuple(sorted((p1, p2, p3, p4)))
			if p3 in points and p4 in points and (square_as_tuple not in squares_found):
				squares += 1
				squares_found.add(square_as_tuple)
	return len(squares_found)
num_tests = int(input())
for i in range(num_tests):
	N = int(input())
	points_set = set()
	for j in range(N):
		(num1, num2) = map(int, input().split())
		points_set.add((num1, num2))
	print(count_squares(points_set))


def count(points_set):
	N = len(points_set)
	points = list(points_set)
	ans = 0
	for i in range(N):
		for j in range(i + 1, N):
			(x1, y1) = points[i]
			(x2, y2) = points[j]
			point_sqr1 = ((x1 + x2) / 2 + (y2 - y1) / 2, (y1 + y2) / 2 - (x2 - x1) / 2)
			point_sqr2 = ((x1 + x2) / 2 - (y2 - y1) / 2, (y1 + y2) / 2 + (x2 - x1) / 2)
			if point_sqr1 in points_set and point_sqr2 in points_set:
				ans += 1
	return ans // 2
num_tests = int(input())
for i in range(num_tests):
	N = int(input())
	points_set = set()
	for j in range(N):
		(num1, num2) = map(int, input().split())
		points_set.add((num1, num2))
	print(count(points_set))


def count(points):
	points.sort()
	all_poiunts = set(points)
	ans = 0
	n = len(points)
	for i in range(n):
		for j in range(i + 1, n):
			(x1, y1) = points[i]
			(x2, y2) = points[j]
			if y2 > y1:
				dx = abs(y2 - y1)
				dy = abs(x2 - x1)
				p3 = (x1 + dx, y1 - dy)
				p4 = (x2 + dx, y2 - dy)
				if p3 in all_poiunts and p4 in all_poiunts:
					ans += 1
	return ans
num_tests = int(input())
for _ in range(num_tests):
	N = int(input())
	points = []
	for _ in range(N):
		temp = input().split()
		points.append((int(temp[0]), int(temp[1])))
	print(count(points))


def count(points):
	points.sort()
	record = set(points)
	sol = 0
	for i in range(len(points)):
		for j in range(i + 1, len(points)):
			(x1, y1) = points[i]
			(x2, y2) = points[j]
			if y2 > y1:
				dx = abs(y2 - y1)
				dy = abs(x2 - x1)
				p3 = (x1 + dx, y1 - dy)
				p4 = (x2 + dx, y2 - dy)
				if p3 in record and p4 in record:
					sol += 1
	return sol
t = int(input())
for i in range(t):
	N = int(input())
	points = []
	for s in range(N):
		temp = input().split()
		points.append((int(temp[0]), int(temp[1])))
	print(count(points))


def count(points):
	points.sort()
	count = 0
	points_set = set(points)
	for i in range(len(points)):
		for j in range(i + 1, len(points)):
			pt1 = points[i]
			pt2 = points[j]
			x1 = pt1[0]
			x2 = pt2[0]
			y1 = pt1[1]
			y2 = pt2[1]
			if y2 > y1:
				dy = abs(y2 - y1)
				dx = abs(x2 - x1)
				pt3 = (x1 + dy, y1 - dx)
				pt4 = (x2 + dy, y2 - dx)
				if pt3 in points_set and pt4 in points_set:
					count += 1
	return count
t = int(input())
for i in range(t):
	N = int(input())
	points = []
	for s in range(N):
		temp = input().split()
		points.append((int(temp[0]), int(temp[1])))
	print(count(points))


def solution(x, y):
	point_set = set()
	for i in range(len(x)):
		point_set.add((x[i], y[i]))
	squares = 0
	for i_idx in range(len(x)):
		for j_idx in range(i_idx + 1, len(x)):
			i = (x[i_idx], y[i_idx])
			j = (x[j_idx], y[j_idx])
			if i[1] < j[1] or (i[1] == j[1] and i[0] >= j[0]):
				(i, j) = (j, i)
			if i[0] >= j[0]:
				continue
			del_x = j[0] - i[0]
			del_y = j[1] - i[1]
			k = (i[0] - del_y, i[1] + del_x)
			l = (j[0] - del_y, j[1] + del_x)
			if k in point_set and l in point_set:
				squares += 1
	return squares
t = int(input())
for test_case in range(t):
	N = int(input())
	x_coords = []
	y_coords = []
	for point in range(N):
		coords = input().split(' ')
		x_coords.append(int(coords[0]))
		y_coords.append(int(coords[1]))
	print(solution(x_coords, y_coords))


def getSquares(x, y):
	z = sorted(zip(x, y))
	point_set = set()
	for i in range(len(z)):
		point_set.add(z[i])
	squares = 0
	for i_idx in range(len(x)):
		for j_idx in range(i_idx + 1, len(x)):
			i = z[i_idx]
			j = z[j_idx]
			mid = ((i[0] + j[0]) / 2, (i[1] + j[1]) / 2)
			del_x = j[0] - i[0]
			del_y = j[1] - i[1]
			if del_x != 0:
				if del_y / del_x >= 0:
					k = (mid[0] - del_y / 2, mid[1] + del_x / 2)
					l = (mid[0] + del_y / 2, mid[1] - del_x / 2)
					if k in point_set and l in point_set and (k != i and l != j):
						squares += 1
	return squares
t = int(input())
for test in range(t):
	n = int(input())
	x = []
	y = []
	for pt in range(n):
		point = input()
		x.append(int(point.split(' ')[0]))
		y.append(int(point.split(' ')[1]))
	print(getSquares(x, y))


def solve(x, y):
	n = len(x)
	pts = set()
	count = 0
	for i in range(n):
		pts.add((x[i], y[i]))
	points = list(pts)
	for i in range(n):
		for j in range(i + 1, n):
			a = points[i]
			c = points[j]
			(b, d) = getOtherPoints(a, c)
			if b in pts and d in pts:
				count += 1
	return count // 2

def getOtherPoints(a, c):
	ax = a[0]
	ay = a[1]
	cx = c[0]
	cy = c[1]
	mid_x = (ax + cx) / 2
	mid_y = (ay + cy) / 2
	delta_x = cx - mid_x
	delta_y = cy - mid_y
	bx = mid_x - delta_y
	by = mid_y + delta_x
	dx = mid_x + delta_y
	dy = mid_y - delta_x
	b = (bx, by)
	d = (dx, dy)
	return (b, d)
t = int(input())
for test in range(t):
	n = int(input())
	x = []
	y = []
	for pt in range(n):
		point = input()
		x.append(int(point.split(' ')[0]))
		y.append(int(point.split(' ')[1]))
	print(solve(x, y))


def solution(x, y):
	points = set()
	for idx in range(len(x)):
		points.add((x[idx], y[idx]))
	n_squares = 0
	for i_idx in range(len(x)):
		for j_idx in range(i_idx + 1, len(x)):
			x_1 = (x[i_idx], y[i_idx])
			x_2 = (x[j_idx], y[j_idx])
			if x_1[1] == x_2[1] and x_1[0] >= x_2[0] or x_1[1] < x_2[1]:
				(x_1, x_2) = (x_2, x_1)
			perp_x = x_2[0] - x_1[0]
			perp_y = x_2[1] - x_1[1]
			z = (x_1[0] - perp_y, x_1[1] + perp_x)
			w = (x_2[0] - perp_y, x_2[1] + perp_x)
			if z in points and w in points:
				n_squares += 1
	return n_squares // 2
t = int(input())
for test_case in range(t):
	N = int(input())
	x_coords = []
	y_coords = []
	for point in range(N):
		coords = input().split(' ')
		x_coords.append(int(coords[0]))
		y_coords.append(int(coords[1]))
	print(solution(x_coords, y_coords))


import sys
t = int(input())
while t:
	n = int(input())
	s = set()
	for i in range(n):
		line = input().split()
		s.add((int(line[0]), int(line[1])))
	count = 0
	a = list(s)
	for i in range(n - 1):
		for j in range(i + 1, n):
			(x1, y1) = (a[i][0], a[i][1])
			(x2, y2) = (a[j][0], a[j][1])
			if x1 > x2:
				tmp = x1
				x1 = x2
				x2 = tmp
				tmp = y1
				y1 = y2
				y2 = tmp
			(x3, y3) = (x2 + (y1 - y2), y2 + (x2 - x1))
			(x4, y4) = (x1 + (y1 - y2), y1 + (x2 - x1))
			if (x3, y3) in s and (x4, y4) in s:
				count += 1
			(x3, y3) = (x2 - (y1 - y2), y2 - (x2 - x1))
			(x4, y4) = (x1 - (y1 - y2), y1 - (x2 - x1))
			if (x3, y3) in s and (x4, y4) in s:
				count += 1
	sys.stdout.write(str(int(count / 4)) + '\n')
	t -= 1