3983 - 三角形统计

题目描述

在平面上有 N 个点,他们的编号为 1 \sim N,其中第 i 个点在平面上的坐标为 x_i,y_i,且满足任意两个点的坐标互不相同

请从给定的 N 个点中,找出三个点,使得三个点满足如下条件:

  1. 三个点恰好能构成直角三角形

  2. 该三角形的一条边平行于 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
说明

样例 1 解释

输入的 4 个点分别为:(1,1), (1,2), (1,3), (2,1)。

以 (1,1) 为直角点,可与以下两组点组成直角三角形:

  1. (1,1), (1,2), (2,1)
  2. (1,1), (1,3), (2,1)

共可以构成 2 个不同的直角三角形,因此输出为 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,且所有点的坐标互不相等。

测试点编号Nx_i,y_i特殊性质
1 \sim 2N=30 \le x_i,y_i \le 10^5
3 \sim 4N \leq 1000 \le x_i,y_i \le 10^5A
5 \sim 6N \leq 1000 \le x_i,y_i \le 10^5B
7 \sim 10N \leq 1000 \le x_i,y_i \le 10^5
11N \leq 10^5-10^5 \le x_i,y_i \le 10^5A
12N \leq 10^5-10^5 \le x_i,y_i \le 10^5B
13 \sim 20N \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 满足该性质。

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 3 枚
难度 基础


上一题 下一题