CF650A 题解-526互联

Problem

Meaning

求曼哈顿距离和欧氏距离相等的坐标组数量。

Solution

这道题用枚举复杂度较高，我们考虑探究当两点的曼哈顿距离与欧氏距离相等时，它们横纵坐标的关系。
如下图所示，\(MO\) 与 \(ON\) 长度之和为 \(M\) 和 \(N\) 两点间的曼哈顿距离，\(MN\) 的长度则为两点间的欧氏距离。此时，在 \(Rt\bigtriangleup MON\) 中，\(MO+ON>MN\)，不符合题意。

所以，当 \(Rt\bigtriangleup MON\) 不存在，即 \(MN\) 与坐标轴平行时，\(MO+ON=MN\)，此时，有 \(M\) 与 \(N\) 的横坐标或纵坐标相等。
我们也可以通过两种距离的计算公式推出这个结论。

设 \(M(x_i,y_i)\)，\(N(x_j,y_j)\)。
当 \(|x_i-x_j|+|y_i-y_j|=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}\) 时，
等式两边平方，得 \((x_i-x_j)^2+2|x_i-x_j||y_i-y_j|+(y_i-y_j)^2=(x_i-x_j)^2+(y_i-y_j)^2\)。
移项，合并同类项得 \(2|x_i-x_j||y_i-y_j|=0\)。
从而有 \(|x_i-x_j|=0\) 或 \(|y_i-y_j|=0\)。
即 \(x_i=x_j\) 或 \(y_i=y_j\)，得证。

所以，我们可以分别记录相同的横坐标出现的次数和相同的纵坐标出现的次数，若某个横坐标或纵坐标出现了 \(k\) 次，那么每两次都可以组成一对，总数应加上 \(C_{k}^{2}=\frac{k!}{2!(k-2)!}=\frac{k(k-1)}{2}\)。
但通过阅读样例 \(2\)，可以发现有相同的点出现，导致我们在累加时将横纵坐标都相等的这些点计了两次，需要排掉一次。设对于某个位置上有 \(q\) 个这样的点，我们应该减去一次这些点两两组合成的坐标组数，即减去 \(C_{q}^{2}=\frac{q!}{2!(q-2)!}=\frac{q(q-1)}{2}\)。

Code

通过三个映射表分别维护每个横坐标出现次数，每个纵坐标出现次数和每个位置上的重点数。
注意开 long long！

#include<bits/stdc++.h>
using namespace std;
long long n,ans;
map<long long,long long> xeql,yeql;
map<pair<long long,long long>,long long> alleql;
long long f(long long x){
	return (x*(x-1))/2;
}
int main(){
	long long temx,temy;
	scanf("%lld",&n);
	for(int i=1;i<=n;++i){
		scanf("%lld%lld",&temx,&temy);
		++xeql[temx];
		++yeql[temy];
		++alleql[{temx,temy}];
	}
	map<long long,long long>::iterator iter1;
	map<pair<long long,long long>,long long>::iterator iter2; 
	for(iter1=xeql.begin();iter1!=xeql.end();++iter1){
		ans+=f(iter1->second);
	}
	for(iter1=yeql.begin();iter1!=yeql.end();++iter1){
		ans+=f(iter1->second);
	}
	for(iter2=alleql.begin();iter2!=alleql.end();++iter2){
		ans-=f(iter2->second);
	}
    printf("%lld",ans);
}