Codeforces 975D. Ghosts

Description

给出一条直线 (a*x+b) 上的 (n) 个点,每一个点有一个速度 ((v_x,v_y)),求 (T=[-oo,oo]) 相交的次数乘以 (2)
题面

Solution

横纵坐标分开考虑
横坐标相等的时刻 (T_x=frac{x_j-x_i}{v_{x_i}-v_{x_j}})
总坐标相等的时刻 (T_y=frac{a(x_j-x_i)}{v_{y_i}-v_{y_j}})
(T_x=T_y)
(v_{y_i}-a*v_{x_i}=v_{y_j}-a*v_{x_j})
用 (map) 记录一下出现次数就行了,注意要减去平行的情况

#include<bits/stdc++.h>
using namespace std;
template<class T>void gi(T &x){
	int f;char c;
	for(f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
	for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f;
}
const int N=2e5+10;
typedef long long ll;
int n,a,b;
map<ll,int>S;
map<pair<int,int>,int>T;
int main(){
  freopen("pp.in","r",stdin);
  freopen("pp.out","w",stdout);
  ll ans=0;
  int x,vx,vy;
  cin>>n>>a>>b;
  for(int i=1;i<=n;i++){
	  gi(x);gi(vx);gi(vy);
	  ll t=vy-1ll*a*vx;
	  ans+=(S[t]-T[make_pair(vx,vy)])<<1;
	  S[t]++;T[make_pair(vx,vy)]++;
  }
  cout<<ans<<endl;
  return 0;
}