13 Codeforces Round 886 (Div. 4)G. The Morning Star（简单容斥）

G. The Morning Star

• 思路：用map记录x，y，以及y-x、y+x
• 从前往后统计一遍答案即可
• 公式$ans+=cnt[x]+cnt[y]-2\ast cnt[x,y]+cnt[y+x]+cnt[y-x]$
• $cnt[x]+cny[y]-2\ast cnt[x,y]$是统计坐标轴方向的，-2倍是需要把本身这个点给减去容斥是减一倍，这里还需要把自己给挖掉
• $cnt[y+x]+cnt[y-x]$是统计对角线方向的。这也是一种常用的表示对角线的技巧

#include <bits/stdc++.h>#define int long long
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define fep(i, a, b) for(int i = (a); i >= (b); --i)
#define _for(i, a, b) for(int i=(a); i<(b); ++i)
#define pii pair<int, int>
#define pdd pair<double,double>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
#define vi vector<int>/** 思路：用map记录x，y，以及y-x、y+x* 从前往后统计一遍答案即可*/
using namespace std;
const int maxn = 2e5 + 10;
pii a[maxn];void solve() {int n;cin>>n;map<int,int>cntx,cnty,cntd,cnts;map<pii,int>cnt;int ans=0;rep(i,1,n){cin>>a[i].x>>a[i].y;}sort(a+1,a+1+n);rep(i,1,n){int x=a[i].x,y=a[i].y;ans+=cntx[x];ans+=cnty[y];//容斥ans-=2*cnt[{x,y}];ans+=cntd[y-x];ans+=cnts[y+x];cntx[x]+=1;cnty[y]+=1;cntd[y-x]+=1;cnts[y+x]+=1;cnt[{x,y}]+=1;}cout<<ans*2<<endl;
}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("C:\\Users\\24283\\CLionProjects\\untitled2\\1.in", "r", stdin);int _;cin >> _;while (_--)solve();return 0;
}