在平面上有 N 个点,他们的编号为 1 \sim N,其中第 i 个点在平面上的坐标为 x_i,y_i,且满足任意两个点的坐标互不相同。
请从给定的 N 个点中,找出三个点,使得三个点满足如下条件:
三个点恰好能构成直角三角形。
该三角形的一条边平行于 x 轴,另一条边,平行于 y 轴。
若两个三角形由完全相同的三个点组成,则认为它们相同;否则认为不同。
请统计出,符合上述条件的不同的三角形,一共有多少个?
第 1 行读入整数 N。
接下来 N 行,读入 N 个点在平面中的坐标,第 i 行读入 x_i,y_i。
输出一个整数,表示符合题目要求的不同三角形的个数。
4 1 1 1 2 1 3 2 1
2
5 1 1 2 1 3 1 4 1 -1 2
0
15 2 -2 3 8 -2 8 7 7 2 1 -9 -3 -4 10 -8 -4 10 4 -9 0 -6 -2 8 0 -3 -6 -6 -3 5 2
5
输入的 4 个点分别为:(1,1), (1,2), (1,3), (2,1)。
以 (1,1) 为直角点,可与以下两组点组成直角三角形:
共可以构成 2 个不同的直角三角形,因此输出为 2。
输入的 5 个点为:(1,1), (2,1), (3,1), (4,1), (-1,2)。
观察所有点可知:本样例中无法构成任何符合要求的直角三角形,输出为 0。
对于 100\% 的测试数据,满足 1 \leq N \leq 10^5,-10^5 \le x_i, y_i \le 10^5,且所有点的坐标互不相等。
| 测试点编号 | N | x_i,y_i | 特殊性质 |
|---|---|---|---|
| 1 \sim 2 | N=3 | 0 \le x_i,y_i \le 10^5 | 无 |
| 3 \sim 4 | N \leq 100 | 0 \le x_i,y_i \le 10^5 | A |
| 5 \sim 6 | N \leq 100 | 0 \le x_i,y_i \le 10^5 | B |
| 7 \sim 10 | N \leq 100 | 0 \le x_i,y_i \le 10^5 | 无 |
| 11 | N \leq 10^5 | -10^5 \le x_i,y_i \le 10^5 | A |
| 12 | N \leq 10^5 | -10^5 \le x_i,y_i \le 10^5 | B |
| 13 \sim 20 | N \leq 10^5 | -10^5 \le x_i,y_i \le 10^5 | 无 |
特殊性质 A:保证读入的 N 个点,其中第 1 \sim N-1 个点的 x 坐标相同,且和第 N 个点的 x 不同,样例 1 满足该性质。
特殊性质 B:保证读入的 N 个点,其中第 1 \sim N-1 个点的 y 坐标相同,且和第 N 个点的 y 不同,样例 2 满足该性质。