题解 P6355 【[COCI2007-2008#3] DEJAVU】
SingularPoint
2020-10-11 20:29:35
### 题目大意
给出坐标系中的$n$个点，求以不同的三个点组成的 **直角边与坐标轴平行的直角三角形**个数。
### 分析
由题意可以知道：如果我们设符合要求的三角形直角顶点坐标为$A(x_1,y_1)$，那么剩下两点坐标一定为$B(x_1,y_i)$、$C(x_j,y_1)$。所以，如果我们确定一个点为直角顶点，那么可以与之配合成为目标三角形的只有是横、纵坐标都与之相同的点。
由此，我们可以考虑用两个数组$sumx$、$sumy$来记录一个横坐标或纵坐标上的点的个数，明显的，当直角顶点为$A(x_1,y_1)$时，可以组成的目标三角形个数为
>$(sumx(x_1)-1)\times(sumy(y_1)-1)$
（注：-1是减去当前所在的点）
由此，我们可以枚举每个点，取出它所在的横、纵坐标，用上面的公式计算出在这个点可以组成的目标三角形个数，累加起来，就是答案啦~
分析结束，上代码！
### Code
**P.S.：$3\leq n<10^5$，日常爆int，不开long long两行泪。**
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=100005;
struct node{
ll x,y;
}p[M];
int n;
ll sx[M],sy[M];
ll ans=0;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&p[i].x,&p[i].y);
sx[p[i].x]++;
sy[p[i].y]++;
}
for(int i=1;i<=n;i++)
ans+=(sx[p[i].x]-1)*(sy[p[i].y]-1);
printf("%lld",ans);
return 0;
}
```
完结撒fa~