Ghosts

Created by LXC on Tue May 23 00:20:54 2023

https://codeforces.com/problemset/problem/975/D

ranting: 2000

tag: geometry, math

题意

给出n个二维平面上的点，这些点在一条直线上 y = a * x + b

每个点都给出了在x轴方向的速度和y轴方向的速度。

每个点都有一个碰撞次数，如果碰到另一个点则会增加该点的碰撞次数。

求所有点的碰撞次数总和。

题解

考虑两个点$(x_i, y_i), (x_j, y_j)$在什么情况下会碰撞。

当同时满足$x_i+ v_{x_i} *t = x_j + v_{x_j} *t$以及$y_i+ v_{y_i} *t = y_j + v_{y_j} *t$时，则会碰撞。

已知$y_i = x_i* a+b$，所以

$\frac{x_i-x_j}{v_{x_j}-v_{x_i}} = t = \frac{y_i-y_j}{v_{y_j}-v_{y_i}} = \frac{a*(x_i-x_j)}{v_{y_j}-v_{y_i}} \Rightarrow \frac{1}{v_{x_j}-v_{x_i}} = \frac{a}{v_{y_j}-v_{y_i}}$

$av_{x_i}-v_{y_i} = av_{x_j}-v_{y_j} $

所有$a*v_{x_i}-v_{y_i}$相等但速度不相等（$v_{x_i} \ne v_{x_j} \wedge v_{y_i} \ne v_{y_j}$）的$(x_i, y_i)$将会相撞

我们统计所有相同速度的频数。

然后用哈希表记录所有$a*v_{x_i}-v_{y_i}$的个数。其中$i<j$

然后对于当前速度$(v_{x_j},v_{y_j})$，哈希表中$a*v_{x_j}-v_{y_j}$的个数乘以当前$(v_{x_j},v_{y_j})$的频数再乘以2（由于两个点碰撞每个点都要增加贡献）

代码

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll n, a, b;
    cin >> n >> a >> b;
    map<pair<ll, ll>, ll> mp;
    for (int i = 0; i < n; i++) {
        ll x, vx, vy;
        cin >> x >> vx >> vy;
        mp[{vx, vy}]++;
    }
    map<ll, ll> cnt;
    ll ans = 0;
    for (auto [i, j] : mp) {
        ans += 2 * cnt[a * i.first - i.second] * j;
        cnt[a * i.first - i.second] += j;
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}