（水题）Codeforces - 650A - Watchmen

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=;i<n;i++){

        scanf("%d%d",&x,&y);

        m[{x,y}]++;

        mx[x]++;

        my[y]++;

    }

    ll ans=;

    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-);

        //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\n",ans/);

}

第二种是容斥原理，对于每个点，重复点在同 $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=;i<n;i++){

        scanf("%d%d",&x,&y);

        mx[x]++;

        my[y]++;

        m[{x,y}]++;

    }

    ll ans=;

    for(auto i:mx){

        ans+=(i.second*(i.second-))/;

    }

    for(auto i:my){

        ans+=(i.second*(i.second-))/;

    }

    for(auto i:m){

        ans-=(i.second*(i.second-))/;

    }

    printf("%lld\n",ans);

}

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