| Codeforces Round 971 (Div. 4) |
|---|
| Закончено |
Сатьяму даны $$$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$$$.
Выведите целое число для каждого набора входных данных — количество различных невырожденных прямоугольных треугольников, которые можно сформировать, выбрав три точки.
351 01 13 05 02 130 01 03 091 02 03 04 05 02 17 18 19 1
4 0 8
Четыре треугольника, о которых идет речь в первом наборе входных данных:
