Quiz
- https://atcoder.jp/contests/abc016/tasks/abc016_4
- 板が何枚に切られるかという問題
AC
図示
- 交差数が分割数に影響する
- (交差数 / 2) + 1
2次元の点は複素数で扱うと楽
- 和・差・積が定義済み
- complex
と書くことが多いので略記を定義した
typedef complex<double> C;
線分の交差判定
- 2つの線分が与えられた時を考える
- ピンクのベクトルから青のベクトルへの外積2つを求め、正負が異なればピンクを挟んで青ベクトルが左右にいる
- もう片方の線分からも同様にチェックする。片方だけのチェックでは、交差していなくても誤判定してしまう（例）
外積とは？
- 3次元ベクトル(以上)で定義される
- ベクトルvからベクトルuに回転させたとき、右ネジの進む向きを向く
- v x u != u x v (非可換)
- 交差判定では外積で求まったベクトルのz成分だけを見ればいい
