競技プログラミング用 知識集積所
ABC418E - Trapezium
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
- 特になし
考え方
台形そのものというよりも、2本の平行線の組を数えればよい。
3点が一直線上にないということは、単純に2点間の方向ベクトルを全て求めて何らかの規格化をし、同一の方向ベクトルの組が何組作れるかを考えればよい。
規格化は、dx>0または(dx==0&&dy>0)、かつdxとdyは互いに素になるようにするのが簡単か。
3点が一直線上にないということは、単純に2点間の方向ベクトルを全て求めて何らかの規格化をし、同一の方向ベクトルの組が何組作れるかを考えればよい。
規格化は、dx>0または(dx==0&&dy>0)、かつdxとdyは互いに素になるようにするのが簡単か。
ただし、これでは平行四辺形を2回数えてしまう。
そこで、方向ベクトルを求める際に向きだけ調整したものも保管しておくことで、平行四辺形の個数も求めて引き算するとよい。
そこで、方向ベクトルを求める際に向きだけ調整したものも保管しておくことで、平行四辺形の個数も求めて引き算するとよい。
