2405.Watchmen

Time Limit: 1s Memory Limit: 256MB

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 (xi,yi).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 |xi-xj|+|yi-yj|. Daniel, as an ordinary person, calculates the distance using the formula 2405_1.png.The success of the operation relies on the number of pairs (i,j) (1 \le i \lt j \le 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.

Input Format(From the terminal/stdin)

Input The first line of the input contains the single integer n (1 \le n \le 200000)- the number of watchmen.Each of the following n lines contains two integers xi and yi (|xi|,|yi| \le 109).Some positions may coincide.

Output Format(To the terminal/stdout)

Output 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.

Sample Input 1

Copy
3
1 1
7 5
1 5
 \n
 · \n
 · \n
 · \n

Sample Output 1

Copy
2
 \n

Sample Input 2

Copy
6
0 0
0 1
0 2
-1 1
0 1
1 1
 \n
 · \n
 · \n
 · \n
  · \n
 · \n
 · \n

Sample Output 2

Copy
11
  \n

Hints

In the first sample, the distance between watchman 1 and watchman 2 is equal to |1-7|+|1-5|=10 for Doctor Manhattan and 2405_2.png for Daniel. For pairs (1,1), (1,5) and (7,5), (1,5) Doctor Manhattan and Daniel will calculate the same distances.

Submit

请先 登录

© 2025 FAQs