Codeforces Round #478 (Div. 2) D. Ghosts

xiaoxiao2021-02-28  15

Codeforces Round #478 (Div. 2)D. Ghosts

点击打开链接

题意:有n个鬼魂在二位坐标上直线行走,某个时间点,它们恰好在一条直线上,给你这条直线y=ax+b中的a和b,然后给你n个点的横坐标和它们在X轴和Y轴的速度,

问从t=−∞  到t=+∞的时间段里,它们相互之间碰撞了几次。

思路:

列方程组:两个人i,j相撞的条件是: 

a*x(i)+b+t*vy(i)=a*xj+b+t*vy(j)   -------纵坐标相等

x(i)+t*vx(i)=x(j)+t*vx(j)-----------横坐标相等

化简得vy(i)-a*vx(i)=vy(j)-a*vx(j),

用一个mapa[]记录pair<Vxi,Vyi>的值,即点i的速度,

一个mapb[]记录a*Vxi-Vyi的值。

即既要满足化简而来的等式,也不能是速度相同的点。

具体代码如下:

#include<bits/stdc++.h> using namespace std; const int maxn = 200000 + 10; const int INF = 2 * int(1e9) + 10; #define ll long long map<pair<ll,ll>,ll> mapa; map<ll,ll>mapb; ll vx[maxn],vy[maxn]; int main() { int n,a,b,x; cin>>n>>a>>b; for(int i=1; i<=n; i++) { scanf("%d%I64d%I64d",&x,&vx[i],&vy[i]); mapa[make_pair(vx[i],vy[i])]++; //记录有多少个这个速度的点 mapb[a*vx[i]-vy[i]]++; //记录有多少个a*Vx-Vy值的个数 } ll ans=0; for(int i=1; i<=n; i++) ans+=mapb[a*vx[i]-vy[i]]-mapa[make_pair(vx[i],vy[i])]; printf("%I64d\n",ans); return 0; }
转载请注明原文地址: https://www.6miu.com/read-1750050.html

最新回复(0)