perogram

D - 一刀両断 〜線分の交差と外積〜

Quiz

Submit

https://atcoder.jp/contests/abc016/submissions/4405573

図示

f:id:peroon:20190227224537j:plain

  • 交差数が分割数に影響する
  • (交差数 / 2) + 1

2次元の点は複素数で扱うと楽

  • 和・差・積が定義済み
  • complexと書くことが多いので略記を定義した
typedef complex<double> C;

線分の交差判定

  • 2つの線分が与えられた時を考える
  • ピンクのベクトルから青のベクトルへの外積2つを求め、正負が異なればピンクを挟んで青ベクトルが左右にいる
  • もう片方の線分からも同様にチェックする。片方だけのチェックでは、交差していなくても誤判定してしまう(例)

f:id:peroon:20190501135453j:plain f:id:peroon:20190227230840j:plain

外積

  • 3次元ベクトル(以上)で定義される
  • ベクトルvからベクトルuに回転させたとき、右ネジの進む向きを向く
  • v x u != u x v (非可換)
  • 交差判定では外積で求まったベクトルのz成分だけを見ればいい

f:id:peroon:20190227230845j:plain