Given N separate integer points on the Cartesian plane satisfying: there is no any three of them sharing a same X-coordinate. Your task is to count the number of rectangles (whose edges parrallel to the axes) created from any four of given points.

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

There are several test cases (ten at most), each formed as follows:
The first line contains a positive integer N (N ≤ 10^{5}).
N lines follow, each containing a pair of integers (each having an absolute value of 10^{9} at most) describing coordinates of a given point.

The input is ended with N = 0.

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

For each test case, output on a line an integer which is the respective number of rectangles found.

----- Sample Input 1 ------ 
6
7 1
3 5
3 1
1 5
1 1
7 5
0
----- Sample Output 1 ------ 
3

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Geometry

Sorting

Mathematics

Data structures

Ad-hoc
Skill types: Sorting

Data structures

Starter code:

Solutions:
def solve(n):
	points = []
	for _ in range(n):
		(x, y) = map(int, input().split())
		points.append([x, y])
	points.sort()
	d = {}
	for i in range(n - 1):
		(x1, y1) = (points[i][0], points[i][1])
		(x2, y2) = (points[i + 1][0], points[i + 1][1])
		if x1 == x2:
			if (y1, y2) not in d:
				d[y1, y2] = 0
			d[y1, y2] += 1
	ans = 0
	for (k, v) in d.items():
		ans += v * (v - 1) // 2
	print(ans)
while True:
	n = int(input())
	if n == 0:
		break
	solve(n)


def count_rectangles(points_set):
	sorted_points = sorted(points_set)
	y_pairs_counts = {}
	p1 = sorted_points[0]
	for p2 in sorted_points[1:]:
		if p1[0] == p2[0]:
			y_pairs_counts[p1[1], p2[1]] = y_pairs_counts.get((p1[1], p2[1]), 0) + 1
		p1 = p2
	return sum([v * (v - 1) // 2 for v in y_pairs_counts.values()])
while True:
	N = int(input())
	if N == 0:
		break
	points_set = set()
	for j in range(N):
		(num1, num2) = map(int, input().split())
		points_set.add((num1, num2))
	print(count_rectangles(points_set))


from collections import defaultdict
while True:
	n = int(input())
	if n == 0:
		break
	(X, Y) = (defaultdict(list), defaultdict(int))
	for i in range(n):
		(p, q) = map(int, input().split())
		X[p].append(q)
	for (k, v) in X.items():
		if len(v) == 2:
			if v[1] < v[0]:
				(v[0], v[1]) = (v[1], v[0])
			Y[v[0], v[1]] += 1
	ans = 0
	for (k, v) in Y.items():
		ans += v * (v - 1) // 2
	print(ans)


def solve(n):
	p = []
	dic = {}
	while n > 0:
		(r, s) = map(int, input().split())
		p.append((r, s))
		n -= 1
	p.sort()
	for i in range(len(p) - 2, -1, -1):
		(x1, y1) = p[i]
		(x2, y2) = p[i + 1]
		if x1 == x2:
			if (y1, y2) in dic.keys():
				dic[y1, y2] += 1
			else:
				dic[y1, y2] = 1
	ans = 0
	for (k, v) in dic.items():
		ans += v * (v - 1) / 2
	return int(ans)
while True:
	n = int(input())
	if n == 0:
		break
	print(solve(n))


while True:
	n = int(input())
	if n == 0:
		break
	a = []
	for i in range(n):
		t = list(map(int, input().split()))
		a.append(t)
	d = dict()
	a.sort(key=lambda x: (x[0], x[1]))
	for i in range(n - 1):
		if a[i][0] == a[i + 1][0]:
			temp = (a[i][1], a[i + 1][1])
			if temp not in d:
				d[temp] = 0
			d[temp] += 1
	ans = 0
	for i in d:
		ans += d[i] * (d[i] - 1) // 2
	print(ans)


n = 1
while n != 0:
	n = int(input())
	if n == 0:
		break
	l = []
	dic = {}
	while n > 0:
		(a, b) = map(int, input().split())
		l.append((a, b))
		n -= 1
	l.sort()
	for i in range(len(l) - 2, -1, -1):
		(x1, y1) = l[i]
		(x2, y2) = l[i + 1]
		if x1 == x2:
			if (y1, y2) in dic.keys():
				dic[y1, y2] += 1
			else:
				dic[y1, y2] = 1
	ans = 0
	for (k, v) in dic.items():
		ans += v * (v - 1) / 2
	print(int(ans))
	n = 1


def snek(n):
	l = []
	for z in range(n):
		(x, y) = map(int, input().split())
		l.append([x, y])
	l.sort()
	d = {}
	for j in range(n - 1):
		(x1, y1) = (l[j][0], l[j][1])
		(x2, y2) = (l[j + 1][0], l[j + 1][1])
		if x1 == x2:
			if (y1, y2) not in d:
				d[y1, y2] = 0
			d[y1, y2] += 1
	ans = 0
	for (k, v) in d.items():
		ans += v * (v - 1) // 2
	print(ans)
while True:
	n = int(input())
	if n == 0:
		break
	snek(n)


def solve(points, N):
	points.sort()
	cnt = {}
	for i in range(N - 1):
		(x1, y1, x2, y2) = (points[i][0], points[i][1], points[i + 1][0], points[i + 1][1])
		if x1 == x2:
			if (y1, y2) not in cnt:
				cnt[y1, y2] = 0
			cnt[y1, y2] += 1
	ans = 0
	for key in list(cnt.keys()):
		value = cnt[key]
		ans += value * (value - 1) // 2
	print(ans)
while True:
	N = int(input())
	if N == 0:
		break
	points = []
	for i in range(N):
		(x, y) = map(int, input().split())
		points.append((x, y))
	solve(points, N)


import collections
n = int(input())
while n != 0:
	points = []
	for _ in range(n):
		points.append(tuple(map(int, input().split())))
	points.sort()
	ans = 0
	sides = collections.defaultdict(int)
	for i in range(n - 1):
		(x1, y1) = points[i]
		(x2, y2) = points[i + 1]
		if x1 == x2:
			ans += sides[y1, y2]
			sides[y1, y2] += 1
	print(ans)
	n = int(input())


import math
while True:
	t = int(input())
	if t == 0:
		break
	arr = [[0 for i in range(2)] for j in range(t)]
	for i in range(t):
		x = input().split()
		arr[i][0] = int(x[0])
		arr[i][1] = int(x[1])
	if t < 4:
		print(0)
	else:
		arr.sort(key=lambda x: (x[0], x[1]))
		dict1 = {}
		i = 0
		while i < len(arr):
			if i + 1 < len(arr) and arr[i][0] == arr[i + 1][0]:
				x = (arr[i][1], arr[i + 1][1])
				if x in dict1:
					dict1[x] += 1
				else:
					dict1[x] = 1
				i += 2
			else:
				i += 1
		sum = 0
		ele = list(dict1.values())
		for i in range(len(ele)):
			val = (ele[i] - 1) * ele[i] // 2
			sum += val
		print(sum)