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

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

D. Ghosts

传送门

昨晚过掉前三题后看了眼D，噫….几何题，溜了溜了，准备明天（今天）的考试去了。

实际上这题只要思路对了操作起来其实很简单。
对于两个起始坐标分别为 (Xi,aXi+b)和(Xj,aXj+b) ( X i , a X i + b ) 和 ( X j , a X j + b ) $(Xi,aXi+b)和(Xj,aXj+b)$的两个来说，他们两个在运动中碰撞当且仅当坐标相同，那么我们可以列出以下两条式子：

Xi+tVXi=Xj+tVXj X i + t V X i = X j + t V X j $Xi+tVXi=Xj+tVXj$
aXi+b+tVYi=aXj+b+tVYj a X i + b + t V Y i = a X j + b + t V Y j $aXi+b+tVYi=aXj+b+tVYj$

解方程得到 atVXj−atVXi=tVYj−tVYi a t V X j − a t V X i = t V Y j − t V Y i $atVXj-atVXi=tVYj-tVYi$
化简得到VYi−aVXi=VYj−aVXj 化 简 得 到 V Y i − a V X i = V Y j − a V X j $化简得到VYi-aVXi=VYj-aVXj$
与此同时，我们还可以得知合速度方向相同的点永远不会相撞，
那么最后的答案就是相同的值的个数减去对应的向量的个数。

#include<cstdio>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<limits.h>
#include<string.h>
#include<map>
#include<list>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;#define inf int(0x3f3f3f3f)
#define mod int(1e9+7)
#define eps double(1e-6)
#define pi acos(-1.0)
#define lson  root << 1
#define rson  root << 1 | 1int n,a,b;struct edge
{ll x,vx,vy;
}p[200005];map<ll, ll >mp1;
map<pair<ll, ll> ,ll >mp2;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>a>>b;mp1.clear();mp2.clear();for(int i=0;i<n;i++){cin>>p[i].x>>p[i].vx>>p[i].vy;ll x=p[i].x;ll vx=p[i].vx;ll vy=p[i].vy;mp1[vy-a*vx]++;mp2[make_pair(vx,vy)]++;}ll sum=0;for(int i=0;i<n;i++){ll x=p[i].x;ll vx=p[i].vx;ll vy=p[i].vy;sum+=mp1[vy-a*vx]-mp2[make_pair(vx,vy)];}cout<<sum<<endl;
}