移动的点
二维平面中有 $n$ 个点。
每个点都在做着匀速运动，其中第 $i$ 个点在 $x$ 轴上的速度为 $V_{xi}$，在 $y$ 轴上的速度为 $V_{yi}$。
这些点从很久之前（$−\infty$ 时刻）就存在，在无限的未来（$+\infty$ 时刻）也将存在，并且会一直保持着它们的运动。
每个点都拥有一个属性值 $EX$，它记录了该点自诞生到现在与其他点相遇的次数，每当该点与其他点在某时某刻相遇，该值就会增加 $1$，关于该属性值，需注意：
- 如果同一时刻同一地点，一个点与多个点相遇，则每个与它相遇的点都会使其 $EX$ 值增加 $1$。
- 两个点发生相遇时，它们的 $EX$ 值都会增加。
由于每个点的运动速度都是恒定的，所以每个点的 $EX$ 值都会在某一时刻达到最大值，并且以后不会再发生变化。
也就是说，不妨设 $n$ 个点的 $EX$ 值之和为 $GX$，即 $GX = \sum\limits_{i=1}^{n} {{EX}_i}$，在某一时刻后，$GX$ 值也将达到最大值并不再增加。
十分巧合的是这 $n$ 个点会在某个时刻排列在同一条直线 $y=ax+b$ 上，每个点在该时刻的具体位置已知。
请你根据这些信息，计算 $GX$ 的最大值。
请注意，所有点的运动并不是从共线那一时刻开始的，所以在发生共线之前，$GX$ 的值可能已经大于 $0$ 了。
输入格式
第一行包含三个整数 $n,a,b$。
接下来 $n$ 行，每行包含三个整数 $x_i,V_{xi},V_{yi}$，其中 $x_i$ 表示第 $i$ 个点在发生共线时所在位置的 $x$ 坐标（由此信息以及之前给定的 $a$ 和 $b$ 的值，即可计算出其所在位置的 $y$ 坐标）。
保证在发生共线时，这 $n$ 个点不存在重合，也就是说输入满足对于所有 $(i,j)$，如果 $i \ne j$，则 $x_i \ne x_j$。
输出格式
输出一个整数，表示 $GX$ 的最大值。
数据范围
前三个测试点满足 $1 \leq n \leq 5$。
所有测试点满足 $1 \leq n \leq 2 \times {10}^{5}$，$1 \leq \left| a \right| \leq {10}^{9}$，$0 \leq \left| b \right| \leq {10}^{9}$，${−10}^{9} \leq x_i,V_{xi},V_{yi} \leq {10}^{9}$。
输入样例1：
4 1 1 1 -1 -1 2 1 1 3 1 1 4 -1 -1
输出样例1：
8
输入样例2：
3 1 0 -1 1 0 0 0 -1 1 -1 -2
输出样例2：
6
输入样例3：
3 1 0 0 0 0 1 0 0 2 0 0
输出样例3：
0
解题思路
当全部点都在直线$y = ax + b$上时，任取两点坐标分别为$(x_i, y_i)$和$(x_j, y_j)$。假设这两个点在$t$时刻相遇，进行正交分解，此时横纵坐标相同，即
\begin{cases}
x_i + v_{xi} \cdot t &= x_j + v_{xj} \cdot t \\
ax_i + b + v_{yi} \cdot t &= ax_j + b + v_{yj} \cdot t
\end{cases}
约去变量$t$，有$$a \times \frac{x_j - x_i}{v_{yj} - v_{yi}} = \frac{x_j - x_i}{v_{xj} - v_{xi}}$$
因为题目保证任意两点的横坐标不同，即$x_j \ne x_i$，因此约去分子得到$v_{yj} - a \cdot v_{xj} = v_{yi} - a \cdot v_{xi}$。记$w_k = v_{yk} - a \cdot v_{xk}$，因此如果两个点能够相遇，那么就有$w_i = w_j$。因此可以开个哈希表统计每个点的$w_k$，如果某个$w_k$有$n$个，意味着这$n$个点的每个点都与其余的$n-1$个点发生碰撞，这$n$个点的总碰撞次数为$n \times (n-1)$。当然还要考虑到如果两个点的相对速度为$0$，即有$v_{xi} = v_{xj},~ v_{yi} = v_{yj}$，那么此时$w_i = w_j$仍然成立，但显然这两个点是不会发生相遇的，因此我们还需要开个哈希表来统计每个点的$(v_{xk},~ v_{yk})$。如果某个有序对$(v_{xk},~ v_{yk})$出现了$m$次，在之前的哈希表我们对这$m$个点统计了$m \times (m-1)$次，因为这$m$个点的相对速度相同不可能相遇，因此需要减去之前统计的$m \times (m-1)$次。
AC代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 typedef long long LL;
5 typedef pair<int, int> PII;
6
7 int main() {
8 int n, a, b;
9 scanf("%d %d %d", &n, &a, &b);
10
11 unordered_map<LL, int> mp1; // 统计wi
12 map<PII, int> mp2; // 统计(Vxi, Vyi)
13
14 while (n--) {
15 int x, vx, vy;
16 scanf("%d %d %d", &x, &vx, &vy);
17 mp1[vy - 1ll * a * vx]++;
18 mp2[{vx, vy}]++;
19 }
20
21 LL ret = 0;
22 for (auto &it : mp1) {
23 ret += it.second * (it.second - 1ll);
24 }
25 for (auto &it : mp2) { // 减去相对速度为0的点
26 ret -= it.second * (it.second - 1ll);
27 }
28 printf("%lld", ret);
29
30 return 0;
31 }
参考资料
AcWing杯 - 第64场周赛：https://www.bilibili.com/video/BV1vY4y1c74i?spm_id_from=333.337.search-card.all.click
标签：yi,xi,个点,cdot,相遇,leq,移动 From： https://www.cnblogs.com/onlyblues/p/16586682.html