← 返回题目列表

Codeforces · 2009/D

D. 萨蒂扬和计数

中文机器翻译题面 查看原题

Satyam 在 2D 坐标平面上被赋予 $$$n$$$ 个不同的点。对于所有给定点 $$$(x_i, y_i)$$$,保证 $$$0 \leq y_i \leq 1$$$。选择三个不同的点作为顶点可以形成多少个不同的非退化直角三角形$$$^{\text{*}}$$$?

如果存在一个点 $$$v$$$,使得 $$$v$$$ 是 $$$a$$$ 的顶点,但不是 $$$b$$$ 的顶点,则两个三角形 $$$a$$$ 和 $$$b$$$ 不同。

输入

第一行包含一个整数 $$$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$$$) — Satyam 可以选择的第 $$$i$$$ 个点。保证所有 $$$(x_i, y_i)$$$ 都是成对不同的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

为每个测试用例输出一个整数,即通过选择三个点可以形成的不同非退化直角三角形的数量。

示例

输入 #1

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

输出 #1

4
0
8

注意

第一个测试用例的四个三角形: