Codeforces #478 Div2 D. Ghosts

なんか面倒な幾何が多いなぁ。
http://codeforces.com/contest/975/problem/D

問題

二次元座標上で同一直線y=ax+b上にいくつかの点がある。
各点は時間にそってそれぞれ等速直線運動しており、それぞれの移動速度が与えられる。
過去から未来にかけて、点同士が遭遇するのは何回か。

解法

直線の直角方向に対する移動速度が等しい点同士で、直線と同じ方向に対する移動速度が異なるものは過去か未来のどちらかでいずれ遭遇する。
よってそれらを求めればよい。
とはいえ愚直に直角方向および平行方向のベクトルを真面目に計算すると、有理数で扱うのも面倒だし小数だと誤差が怖い。
直線からY軸方向に離れる速度と、X軸方向の移動速度で同じように考えても差し支えない。こちらだと除算が登場せずあっさり書ける。

ll N,A,B;
map<ll,ll> tot;
map<pair<ll,ll>,ll> tot2;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B;
	ll ret=0;
	FOR(i,N) {
		cin>>r>>x>>y;
		
		ll X=x;
		ll Y=y-A*x;
		
		ret+=tot[Y]-tot2[{X,Y}];
		tot[Y]++;
		tot2[{X,Y}]++;
	}
	cout<<ret*2<<endl;
}

まとめ

これはシンプルな解法を思いつけたと思ったけど、同じ人結構いたかも。