多分想定解っぽい解法で解いて、だいたい合っている実装をしたつもりだったのですが、 どうも double の精度落ちで WA 出てしまっていたような気がしますね……。

計算量も余裕がありますし、Python で解けば通りそうだな……とは思ったのですが、 入出力周り調べるのが面倒になってしまい WA で放置してしまいました。

レートが少し下がってしまい残念ですが……、 他の言語でも素早く回答できるようにしておきたいと思いました。