Codeforces Round #478 (Div. 2) D Ghosts 会超时的判断两个之间关系，可以用map-白红宇

Codeforces Round #478 (Div. 2) D Ghosts 会超时的判断两个之间关系，可以用map

阅读量：4613 次

发布时间：2019-06-09

本文共 949 字，大约阅读时间需要 3 分钟。

给出起始坐标（x,y）要充分利用题目条件，最好全都列出来

运动方向（Vx,Vy）

很容易得到判断两个是否相碰

(gho[a].y-gho[b].y)*1.0/(gho[a].vy-gho[b].vy)==(gho[a].x-gho[b].x)*1.0/(gho[a].vx-gho[b].vx)

但是每一个都判断双重循环肯定超时

不要忘了题目为什么给定初始位置在一条直线上，而不是任意位置，肯定是为了化简上面式子！

所以最后化得 vyi−a∗vxi=vyj−a∗v

所以用map 存储，看有没有符合的

同时要减去平行的那些

转自https://www.cnblogs.com/ZhenghangHu/p/8982277.html

include
    
     #include
     #define ll long long#define MAXN 200000using namespace std;ll n,a,b,ans,parallel;map
      
        m;map< pair
       
        ,int> p;int main(){    cin>>n>>a>>b;    for(int i=1;i<=n;i++){        int x,Vx,Vy; scanf("%d%d%d",&x,&Vx,&Vy);        //每个维护出来a*Vx-Vy        ll key = a*Vx-Vy;        ans+=m[key];//相同key的能collide         m[a*Vx-Vy]++;        parallel+=p[ make_pair(Vx,Vy) ];//同是1，2 就是平行，一个1，2 一个2，4 虽然方向平行，但是可能反方向的，会可能相碰，他们vy-a*vx不相等所以不用考虑        p[  make_pair(Vx,Vy)  ]++;    }    cout<<(ans-parallel)*2;        return 0; }