CodeForces - 651C-白红宇

CodeForces - 651C

阅读量：5020 次

发布时间：2019-06-12

本文共 2537 字，大约阅读时间需要 8 分钟。

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 $\text{[math]}$ .

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.

Input

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| ≤ 10⁹).

Some positions may coincide.

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.

Example

Input

3 1 1 7 5 1 5

Output

Input

6 0 0 0 1 0 2 -1 1 0 1 1 1

Output

Note

In the first sample, the distance between watchman 1 and watchman 2 is equal to |1 - 7| + |1 - 5| = 10 for Doctor Manhattan and $\text{[math]}$ for Daniel. For pairs (1, 1), (1, 5) and (7, 5), (1, 5) Doctor Manhattan and Daniel will calculate the same distances.

对题目给出的条件化简，得知满足条件的一对点的关系为（x1==x2||y1==y2)

直接用数组存储，然后每个点之间进行比较的时间复杂度为O（n^2），题目中n=2e5，因此要采用降低时间复杂度的方法，那么使用map是最佳的选择。

事实上，除去重合的点的情况，我们不需要知道点的两个坐标，只要知道一条线上有多少个点，若一条线有n个点，则该线上有n（n-1）/2对点满足题目条件。

那么考虑重合的点，若有n个点坐标为（x，y），那么在x线和y线上，这n个点被统计了两次，则减去n（n-1）/2对点即可。

综上，用三个map分别存储x坐标，y坐标和重复的点，代码如下：

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            using namespace std;const int MAX=2e5+10;#define INF 0x7fffffff#define ll long long#define FOR(i,n) for(i=1;i<=n;i++)#define mst(a) memset(a,0,sizeof(a))typedef pair
             
               p;map
              
                x,y;map
               
                 mp;int main(){ ll m,n,i,j,a,b,ans=0; cin>>n; FOR(i,n) { cin>>a>>b; x[a]++; y[b]++; mp[p(a,b)]++; } map
                
                 ::iterator it; map
                 
                  ::iterator itt; for(it=x.begin();it!=x.end();it++) { j=it->second; ans+=j*(j-1)/2; } for(it=y.begin();it!=y.end();it++) { j=it->second; ans+=j*(j-1)/2; } for(itt=mp.begin();itt!=mp.end();itt++) { j=itt->second; ans-=j*(j-1)/2; } cout<
                  
                   <

转载于:https://www.cnblogs.com/qq936584671/p/7125844.html

你可能感兴趣的文章