原题链接

题目

题目描述

在一个平面上有n个点，并且这n个点在某一时刻都在同一条直线y=ax+b上，要我们求最终所有点的相遇次数（a和b相遇，b和a相遇，不属于同一情况，相遇次数都要加一）。题目上还说时间的范围是（负无穷到正无穷）既时间可以随意倒流。

思路分析

如果说某一时刻所有点都在同一条直线上，我们不妨先讨论一下每对点的相遇条件。

因为每个点的速度方向未知，我们先求一个点相对于另外一个点的相对速度，如果两个点可以相遇的话，那么相对速度的方向一定沿着直线方向。

1.png

对于任意一对点a,b,如果要满足a相对于b的速度在直线$y=ax+b$上，那么相对合速度的方向向量的斜率必然等于$a$
既

$(v_{ay}-v_{by})/(v_{ax}-v_{bx})=a$
$(v_{ay}-v_{by})=a(v_{ax}-v_{bx})$
化简得： $av_{ax}-v_{ay}=av_{bx}-v_{by} (v_{ax}\not=v_{bx},v_{ay}\not=v_{by})$ ---- 1

也就是说只要两个点满足1条件那么这两个点就一定可以相遇

算法分析

我们由上面的分析推导出了两点相遇所需要满足的条件，接下来的任务就是如何找到满足这个条件的点，观察取值范围可得$1≤n≤2×10^5$，如果我们暴力的先遍历第一个点再遍历第二个点，那么此时的时间复杂度为$O(n^2)$，很明显算法会超时TLE，因此我们可以使用哈希表统计每个点的$av_{x}-v_{y}$属性出现次数，最后再遍历每个点加上该属性出现的次数，再减去相对静止的点，最后累加起来便是我们的答案。

代码 时间复杂度$O(n)$

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

map<PII,int> m; //用于查找相对静止的点
unordered_map<LL,int> h; //用于统计相遇次数
vector<PII> vs; //存储每个点的vx和vy
LL res; //答案可能会爆int注意用long long存储

int main()
{
    int n,a,b;
    cin>>n>>a>>b;
    while(n--)
    {
        int x,vx,vy;
        cin>>x>>vx>>vy;
        vs.push_back({vx,vy}); //依次读入每个点
        h[(LL)a*vx-vy]++; //统计次数
        m[{vx,vy}]++;
    }
    for(auto v : vs)
    {
        LL t = (LL)a*v.first - v.second;
        res += h[t] - m[v]; //答案
    }
    cout<<res<<endl;
    return 0;
}