（水题）Codeforces

http://codeforces.com/contest/650/problem/A

一开始想了很久都没有考虑到重复点的影响，解欧拉距离和曼哈顿距离相等可以得到 $x_i=x_j$ 或 $y_i=y_j$ ，假如无重复的话就是分别记录 $x$ 和 $y$ 的值然后 $ans+=mx[i]-1,ans+=my[i]-1$ ，就可以了。

那么有重复的话，有两种解决方法，第一种是分类讨论，就是分重复点和同 $x$ 其他点连、重复点和同 $y$ 其他点连、重复点自己连。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long

int n,x,y;
map<int,int> mx;
map<int,int> my;

map<pair<int,int>,int > m;




int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&x,&y);
        m[{x,y}]++;
        mx[x]++;
        my[y]++;
    }

    ll ans=0;
    for(auto i:m){
        //cout<<"i="<<i.first.first<<" "<<i.first.second<<endl;
        ans+=1ll*i.second*(mx[i.first.first]-i.second)+1ll*i.second*(my[i.first.second]-i.second)+1ll*i.second*(i.second-1);
        //cout<<"x="<<i.second*(mx[i.first.first]-i.second)<<endl;
        //cout<<"y="<<i.second*(my[i.first.second]-i.second)<<endl;
        //cout<<"s="<<i.second*(i.second-1)<<endl;

        //cout<<ans<<endl;
    }

    printf("%lld
",ans/2);
}

第二种是容斥原理，对于每个点，重复点在同 $x$ 时与同 $y$ 时分别计算了一次，只要减去重复点自连的数量就可以了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long

int n,x,y;
map<int,ll> mx;
map<int,ll> my;

map<pair<int,int>,ll> m;




int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&x,&y);
        mx[x]++;
        my[y]++;
        m[{x,y}]++;
    }

    ll ans=0;
    for(auto i:mx){
        ans+=(i.second*(i.second-1))/2;
    }
    for(auto i:my){
        ans+=(i.second*(i.second-1))/2;
    }
    for(auto i:m){
        ans-=(i.second*(i.second-1))/2;
    }


    printf("%lld
",ans);
}

 顺带一提还在乘法爆int了，真的服气。