CF650A.Watchmen
普及/提高-
通过率:0%
时间限制:3.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Watchmen are in a danger and Doctor Manhattan together with his friend Daniel Dreiberg should warn them as soon as possible. There are n watchmen on a plane, the i-th watchman is located at point (x__i, y__i).
They need to arrange a plan, but there are some difficulties on their way. As you know, Doctor Manhattan considers the distance between watchmen i and j to be |x__i - x__j| + |y__i - y__j|. Daniel, as an ordinary person, calculates the distance using the formula
.
The success of the operation relies on the number of pairs (i, j) (1 ≤ i < j ≤ n), such that the distance between watchman i and watchmen j calculated by Doctor Manhattan is equal to the distance between them calculated by Daniel. You were asked to compute the number of such pairs.
守望者们正处于危险之中,曼哈顿博士与其朋友丹尼尔·德雷伯格必须尽快向他们发出警报。平面上共有 n 名守望者,其中第 i 名守望者位于点 (xi,yi)。
他们需要制定一个行动计划,但在执行过程中遇到了一些困难。众所周知,曼哈顿博士计算守望者 i 与守望者 j 之间的距离采用的是曼哈顿距离:∣xi − xj∣ + ∣yi − yj∣;而丹尼尔作为一名普通人,则使用欧几里得距离公式计算:
。
此次行动的成功取决于满足如下条件的数对 (i,j)(其中 1 ≤ i < j ≤ n)的个数:即曼哈顿博士所计算的守望者 i 与守望者 j 之间的距离,恰好等于丹尼尔所计算的二者之间的距离。你需要计算出满足该条件的数对个数。
输入格式
The first line of the input contains the single integer n (1 ≤ n ≤ 200 000) — the number of watchmen.
Each of the following n lines contains two integers x__i and y__i (|x__i|, |y__i| ≤ 109).
Some positions may coincide.
输入的第一行包含一个整数 n(1≤n≤200000)—— 表示守卫的人数。
接下来的 n 行,每行包含两个整数 xi 和 yi(∣xi∣,∣yi∣≤109)。
某些位置可能重合。
输出格式
Print the number of pairs of watchmen such that the distance between them calculated by Doctor Manhattan is equal to the distance calculated by Daniel.
输出满足以下条件的守夜人对数:由曼哈顿博士计算出的距离等于由丹尼尔计算出的距离。
输入输出样例
输入#1
3 1 1 7 5 1 5
输出#1
2
输入#2
6 0 0 0 1 0 2 -1 1 0 1 1 1
输出#2
11
说明/提示
In the first sample, the distance between watchman 1 and watchman 2 is equal to |1 - 7| + |1 - 5| = 10 for Doctor Manhattan and
for Daniel. For pairs (1, 1), (1, 5) and (7, 5), (1, 5) Doctor Manhattan and Daniel will calculate the same distances.
在第一个样例中,守卫 1 与守卫 2 之间的距离,对于曼哈顿博士而言为 ∣1 − 7∣ + ∣1 − 5∣ = 10,而对于丹尼尔而言则为
。对于点对 (1, 1)、(1, 5) 和 (7, 5)、(1, 5),曼哈顿博士与丹尼尔计算出的距离相同。
输入解题思路,AI测评打分。不知道怎么写?