一道 tang problem，浪費我大半個下午，使我十分痛苦，嗚嗚嗚嗚。

題意概括

我們有 \(N\) 個點，要求 \(\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}dis(P_i,P_j)\)

\(P_i\) 指的是第 \(i\) 個點。

我們定義 \(dis(P_i,P_j)\) 為從 \(P_i\) 到 \(P_j\) 的最小操作次數(shù)。

關于操作，我們假設現(xiàn)在處于 \((x,y)\)，我們可以到達 \((x+1,y+1)\)，\((x+1,y-1)\)，\((x-1,y+1)\)，\((x-1,y-1)\)。

就是這個亞子。

雜技吧做？

怎么辦?。。≡趺崔k！??！怎么辦?。?！

勞資根本不會嗚嗚嗚嗚。

我們先考慮一下一個 \(dis\) 怎么求，不然暴力都不行。

我去理性思考了一波，有的點直接確實沒法到達，我們從圖上難以分析。

這個問題就是 \((x_i-x_j,y_i-y_j)\)，我們可以選擇去每一次將這么兩個數(shù)任何一個加一或者減一。

我們驚人的發(fā)現(xiàn)了一個秘密的事情，辣就是這個東西如果加起來是偶數(shù)才行，主要是這個東西總體上不變或者加二減二。

所以我們按照 \(x+y\) 的奇偶性分成兩類。

這樣我們就能在每一類上求出來可能的貢獻了。

對于兩個，這個貢獻是 \(max(|x_1-x_2|,|y_1-y_2|)\)。

所以我們起碼會暴力了，但是我不到這個怎么搞正解......

所以我們?nèi)タ匆豢催@個東西是什么玩意。

所有的問題其實就在這 \(max\) 上了，有這個東西就讓我很絕望，所以我發(fā)現(xiàn)了世界的真相。

這個東西不就是切比雪夫距離嘛?。?！

大家都知道，切比雪夫距離和曼哈頓距離是闊以相互轉(zhuǎn)化的。

放一下怎么轉(zhuǎn)化，防止之后我忘掉......

\((x,y)\to(x+y,x-y)\)，原坐標中曼哈頓距離等于新坐標中切比雪夫距離。

\((x,y)\to(\frac{x+y}{2},\frac{x-y}{2})\)，原坐標中切比雪夫距離等于新坐標中曼哈頓距離。

我們就直接轉(zhuǎn)換，這個/2到最后處理，因為我們不方便搞小數(shù)。

就這么轉(zhuǎn)化一波，問題就是求到所有點的曼哈頓距離就行了。

wow，沒辣。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=1e6+116;
int n, ans=0;
vector <int> vec[4];
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin>>n;
	for(int i=1,x,y; i<=n; ++i){
		cin>>x>>y;
		if((x+y)%2==0){
			vec[0].push_back(x+y);
			vec[1].push_back(x-y);
		}else{
			vec[2].push_back(x+y);
			vec[3].push_back(x-y);
		}
	}
	for(int i=0; i<4; ++i){
		sort(vec[i].begin(),vec[i].end());
		int siz=vec[i].size();
		for(int j=0; j<siz; ++j){
			ans+=vec[i][j]*(2*j+1-siz);
		}
	}
	cout<<ans/2<<'\n';
	return 0;
}