Google Code Jam 2019 Round 2 A. New Elements: Part 1

0完だった。。。(点数分布的にAのlargeは通さないとACDのsmallだけでは無理そうだったので時間をかけてたけどsmallすら通せなかった・・・)

問題

CodiumとJamariumという新しい元素を研究しており、これらの原子量に関する統計を調べたいと思っている。
過去の研究より、これらの原子量は厳密に正の値であることはわかっている。

今、N個の分子が与えられている。この分子は上記の2つの原子のみが何個か組み合わさって構成されており、i番目の分子のそれぞれの原子の構成要素数が(Ci, Ji)で与えられる。
分子の重さは、原子量の合計値で表される。

最初の調査として、原子量によってはこの分子を重さ順に並べたいと思っており、「厳密に増加するように並べる並べ方が何通りありえるか？」を知りたい。何通りあるか、答えよ。

例：分子が「(1,1), (2,1), (1,2)」の3つの場合、
Codiumの原子量がJamariumの原子量よりも重い場合は、(1,1), (1,2), (2,1)。
Jamariumの原子量がCodiumの原子量よりも重い場合は、(1,1), (2,1), (1,2)。
同じ原子量の場合は、(2,1)と(1,2)が同じ分子の重さになってしまうため、厳密に増加しないため、条件を満たさない。

制約

1 <= T <= 100
1 <= Ci, Ji <= 10^9
与えられる分子で構成要素が同じものはない
2 <= N <= 300
制限時間は20秒以内
メモリ制限は1GB

解法

元々の原子量がわかっていないので、それを変数として考えたい。
それぞれの原子量を(x, y)と考えてもよいが、片方の原子量がXとして、もう片方はその比率wをかけたX*wで考えると、定数Xが与えられた下では1変数wだけで扱える。
そこで、Codiumの原子量をXとしてJamariumの原子量をX*wとして考える。

i番目の分子の重さは、「Ci * X + Ji * X * w = X * ( Ci + Ji * w)」と書ける。
問題文の条件から、0 < wである。
ここで、各分子の重さを横軸w、縦軸分子の重さとした2次元平面にプロットすると、各分子の重さは直線で表現でき、wがw'の場合の順序はグラフのw=w'と直線の交点(下から上にぶつかる順)になる。

ここで、プロット図を観察すると、交点の位置は同じ重さになっている点なので、上記の条件を満たさない、かつ、その左右で分子の重さの大小関係が必ず入れ替わっているということがわかる。
ただし、Sampleの#2のような交点が同じwで2つ以上ある場合やw=0の点で交点がある場合もあるので、ユニークや0になる場合を含めずにカウントしてあげれば、「その交点があるwの数+1」の領域が並べ方の数になる。

2つの直線の交点は、Xは関係しないので直線を「Ci + Ji * w」とすると、
y=ax+bとy=cx+dの交点はa!=cの時w=(d-b)/(a-c)になるので、それを使えばよい。
小数で扱うと誤差が怪しいので、有理数でカウントする(gcdなどで既約にして扱えばよい)。