C2. Power Transmission (Hard Edition)

Quiz

https://codeforces.com/contest/1163/problem/C2

Submit

https://codeforces.com/contest/1163/submission/54005559

解法

  • 2点から直線が求まるので、係数a, b, cで表現する
    • この時、係数を定数倍すると一致するものに注意する
    • (a, b, c) = (1, 2, 3), (10, 20, 30), (-1, -2, -3)は同一の直線
  • 平行だと交わらないので、傾きごとにまとめて管理する

直線の方程式

f:id:peroon:20190512044509j:plain

  • この表現だとy軸に平行な直線、x軸に平行な直線も同一に扱える
  • 同一の直線を重複して数えないようにする
    • スケールを合わせるためにgcd(a, b, c)で割る
    • aが負ならa, b, cに-1をかける
    • a==0, bが負ならa, b, cに-1をかける (忘れがち)