Codeforces Round #346 (Div. 2) D. Bicycle Race

http://codeforces.com/contest/659/problem/D

問題概要

与えられたコースでサイクリングをする。右折・左折をせずに真っ直ぐ進んだら湖に落ちてしまうような場所は何箇所あるだろうか。

なお与えられるコースは時計回りであることが保証されている。

解法

危険な場所というのはどういう場所だろうか。少し複雑なコースを作ってみよう。

左折箇所がすべて危険だと分かる。

右折か左折かを判定するのは外積の符号を見るのが楽。

Codeforces Round #346 (Div. 2) D. Bicycle Race

本番では無駄にコースが時計回りか反時計回りかを判定をしてしまった。