计算几何

Acwing 4508. 移动的点

二维平面中有 $n$ 个点。
每个点都在做着匀速运动，其中第 $i$ 个点在 $x$ 轴上的速度为 $V_{x_i}$，在 $y$ 轴上的速度为 $V_{y_i}$。
这些点从很久之前（$-∞$ 时刻）就存在，在无限的未来（$+∞$ 时刻）也将存在，并且会一直保持着它们的运动。
每个点都拥有一个属性值 $EX$，它记录了该点自诞生到现在与其他点相遇的次数，每当该点与其他点在某时某刻相遇，该值就会增加 $1$，关于该属性值，需注意：
如果同一时刻同一地点，一个点与多个点相遇，则每个与它相遇的点都会使其 $EX$ 值增加 $1$。
两个点发生相遇时，它们的 $EX$ 值都会增加。
由于每个点的运动速度都是恒定的，所以每个点的 $EX$ 值都会在某一时刻达到最大值，并且以后不会再发生变化。
也就是说，不妨设 $n$ 个点的 $EX$ 值之和为 $GX$，即 $GX = \sum\limits_{i=1}^nEX_i$，在某一时刻后，$GX$ 值也将达到最大值并不再增加。
十分巧合的是这 $n$ 个点会在某个时刻排列在同一条直线 $y=ax+b$ 上，每个点在该时刻的具体位置已知。
请你根据这些信息，计算 $GX$ 的最大值。
请注意，所有点的运动并不是从共线那一时刻开始的，所以在发生共线之前，$GX$ 的值可能已经大于 $0$ 了。
输入格式
第一行包含三个整数 $n,a,b$。
接下来 $n$ 行，每行包含三个整数 $x_i,V_{x_i},V_{y_i}$，其中 $x_i$ 表示第 $i$ 个点在发生共线时所在位置的 $x$ 坐标（由此信息以及之前给定的 $a$ 和 $b$ 的值，即可计算出其所在位置的 $y$ 坐标）。
保证在发生共线时，这 $n$ 个点不存在重合，也就是说输入满足对于所有 $(i,j)$，如果 $i \neq j$，则 $x_i \neq x_j$。
输出格式
输出一个整数，表示 $GX$ 的最大值。
数据范围
前三个测试点满足 $1 \le n \le 5$。
所有测试点满足 $1 \le n \le 2 \times 10^5$，$1 \le |a| \le 10^9$，$0 \le |b| \le 10^9$，$-10^9 \le x_i,V_{x_i},V_{y_i} \le 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

思路：
一个比较难想的点是考虑相对速度!

import java.util.*;
public class Main {
    static final int N = 200010;
    static int n, a, b;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        a = sc.nextInt();
        b = sc.nextInt();
        Map<Long, Integer> map = new HashMap<>();
        Map<Long, Integer> vis = new HashMap<>();
        long res = 0;
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt(), vx = sc.nextInt(), vy = sc.nextInt();
            long p = vy - 1L * a * vx, hash = ((long)(vx) << 32) + vy;
            int c1 = map.getOrDefault(p, 0);
            int c2 = vis.getOrDefault(hash, 0);
            res += (c1 - c2) * 2;
            map.merge(p, 1, Integer::sum);
            vis.merge(hash, 1, Integer::sum);
        }
        System.out.println(res);
    }
}