ABC 401-500/ABC442E - Laser Takahashi - 競技プログラミング用 知識集積所

---

問題

ABC442E

必要知識

B以下レベルの内容は省略

• 偏角ソート※
• 二分探索※

考え方

全てのデータについて偏角ソート※を行えば、あとは二分探索※で簡単。
問題は、偏角ソート※のatan2()関数※の精度問題2つ。

座標の値の大きさがMくらいまであると、2つの角度の差は最小でおよそ1/M^2になる。
そのため、double型では精度が足りず、long double型※を用いないと、非常に近い2つの角度が同一と判定されてしまう。

また、(1,2)と(3,6)みたいな値の組が、long double型※にしたときの末尾の1bitで誤差を生じて不一致と判定される可能性があり、これも防がなければならない。
これは、(x,y)が互いに素でなければ、双方を最大公約数で割ってからatan2()関数※に渡すことで防げる。

以上2つの対応をきちんとやれば、あとは基礎的な問題。

解答例

解答例

注意点

別解

小数は一致判定に問題ありということで、整数だけでどうにかする方法。
0<=y<=xという前提で考える。
異なるが近い2つのy/xの差は、小さくても1/M^2以上。
つまり、M^2*y/xの整数部分に対応付ければ、その整数でのソートが偏角ソートの代用になる。
とはいえM^2*y/xを愚直にやるとlong long型をはみ出してしまうので、

M*y/x*M + M*y%x*M/x

という形で計算する。
これは、1回Mを掛けた段階でxで割った商部分と余り部分に分けてから2回目のMを掛けることで、long long型をはみ出さないようにしてある。
また、これは偏角がπ/4までしか対応していないので、全平面を適当に折りたたむことで任意の偏角に対応させる。
詳しくは解答例参照。
解答例