Codeforces 975D Ghosts （几何数学+思维）

Codeforces 975D Ghosts （几何数学+思维）

题目链接

题意：已知在一条直线y=a*x+b上存在n个点（给出n，a，b），随后n行每行是一个点的信息（x ， Vx，Vy）,表示该点的在x轴上的坐标是x，且（x，y）会随时间变化【x'=x+t*Vx，y'=a*x+b+t*Vy】,这里定义了每个点都有初始权值为0，当某一时刻与其他点相遇，这两个点的权值都会+1，问你负无穷t到无限时间过后所有点的权值总和为多少。

解法：（这里直接搬原题解，因为它是分开算Tx和Ty的，最后令Tx==Ty这样可以避免算漏了2个点运动变化率相同的情况）

对X分析：X0i+VxiTx=X0j+VxjTx

得到：Tx=(X0i−X0j)/(Vxj−Vxi)

同理对Y分析得到：Ty=(aX0i−aX0j+b−b)/(Vyj−Vyi)

由Tx=Ty有：(X0i−X0j)/(Vxj−Vxi)=(aX0i−aX0j)/(Vyj−Vyi)

化简得：1/(Vxj−Vxi)=a/(Vyj−Vyi)

因此当(Vxj−Vxi)！=0 且 (Vyj−Vyi) ！= 0  时有 aVxj−Vyj=aVxi−Vyi

那么我们只需要处理出相同的aVx - Vy 的数量在减去Vxi == Vyj 且Vyi == Vyj 的即可。

代码如下：

#include<cstdio>  
#include<algorithm>  
#include<vector>  
#include<queue>  
#include<string>  
#include<cstring>  
#include<iostream>  
#include<map>
using namespace std;
#define ll long long  
#define inf 0x3f3f3f3f
ll n, a, b, x, vx, vy;
map<pair<ll, ll>, ll>par;
map<ll, ll>cnt;
int main() {while (~scanf("%lld%lld%lld", &n, &a, &b)) {par.clear();cnt.clear();for (int i = 0; i < n; i++) {scanf("%lld%lld%lld", &x, &vx, &vy);cnt[a*vx - vy]++;par[make_pair(vx, vy)]++;}ll ans = 0;for (map<ll, ll>::iterator it = cnt.begin(); it != d(); it++)ans += (it->second)*(it->second - 1);for (map<pair<ll, ll>, ll>::iterator it = par.begin(); it != d(); it++)ans -= (it->second)*(it->second - 1);printf("%lldn", ans);}return 0;
}