Сатьяму даны \(n\) различных точек на двумерной координатной плоскости. Гарантируется, что \(0 \leq y_i \leq 1\) для всех заданных точек \((x_i, y_i)\). Сколько различных невырожденных прямоугольных треугольников\(^{\text{∗}}\) можно сформировать, выбрав три различные точки в качестве его вершин?
Два треугольника \(a\) и \(b\) различны, если существует точка \(v\), такая что \(v\) является вершиной \(a\), но не является вершиной \(b\).
\(^{\text{∗}}\)Невырожденный прямоугольный треугольник имеет положительную площадь и внутренний угол \(90^{\circ}\).
Первая строка содержит целое число \(t\) (\(1 \leq t \leq 10^4\)) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит целое число \(n\) (\(3 \leq n \leq 2 \cdot 10^5\)) — количество точек.
Следующие \(n\) строк содержат по два целых числа \(x_i\) и \(y_i\) (\(0 \leq x_i \leq n\), \(0 \leq y_i \leq 1\)) — \(i\)-я точка, которую Сатьям может выбрать. Гарантируется, что все \((x_i, y_i)\) попарно различны.
Гарантируется, что сумма \(n\) по всем наборам входных данных не превышает \(2 \cdot 10^5\).
Выведите целое число для каждого набора входных данных — количество различных невырожденных прямоугольных треугольников, которые можно сформировать, выбрав три точки.
Четыре треугольника, о которых идет речь в первом наборе входных данных:
3 5 1 0 1 1 3 0 5 0 2 1 3 0 0 1 0 3 0 9 1 0 2 0 3 0 4 0 5 0 2 1 7 1 8 1 9 1
4 0 8
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач