题解 CF1850G The Morning Star

· · 题解

题意

给你 n 个点的坐标，你需要找出有多少组不重合的点满足一个点在另一个点的正北、正南、正东、正西、西北、东北、西南、东南方向。

分析

只需要记录每一行、每一列、每一条斜线上有多少个点即可。

设当前行、列、斜线上有 x 个点，那么答案就为 x(x-1)。

问题在于如何记录，对于行列，我使用了 std::map，斜线就可以用一个 std::pair<int,int> 记录函数解析式。

时间复杂度 O(n \log n)。

代码

//the code is from chenjh
#include<cstdio>
#include<map>
#include<utility>
typedef long long LL;
typedef std::pair<int,int> PII;
int n;
std::map<int,int> H,L;
std::map<PII,int> M;
void solve(){
    scanf("%d",&n);
    H.clear(),L.clear();
    M.clear();
    for(int i=1,x,y;i<=n;i++){
        scanf("%d%d",&x,&y);
        ++H[x],++L[y];//记录行、列。
        ++M[{1,-x+y}],++M[{-1,x+y}];//上升的函数（k=1）和下降的函数（k=-1）。
    }
    LL ans=0;
    for(PII x:H) ans+=(LL)x.second*(x.second-1);//依次统计答案。
    for(PII x:L) ans+=(LL)x.second*(x.second-1);
    for(std::pair<PII,int> x:M) ans+=(LL)x.second*(x.second-1);
    printf("%lld\n",ans);
}
int main(){
    int T;scanf("%d",&T);
    while(T--) solve();
    return 0;
}