|
これは、Competitive Programming Advent Calendar Div2014の9日目の記事です。
誤差死したときはlong doubleにし、TLEしたときはdoubleにできるように最初からtypedefしておくと便利です。
座標の範囲が[-1000:1000]だとEPS=1e-8を使うというのを基準にしていて、相対誤差っぽく[-10000:10000]だとEPS=1e-7とかにすると苦しむことが減ります。
与えられた全ての点を原点を中心に少しだけ回転させる。
スラブ分割（コンピュータ・ジオメトリ P.149）する時など、x座標が同じ頂点があって縮退している場合に縮退が解けます。
例題：最終防衛線
上と同じタイプの縮退が解けます。
座標に小さな乱数（ただしEPSよりは十分大きい）を追加して縮退を解く。
ただし、実際に値を出すときは縮退前の座標を使わないとちょっとずれてWAの原因になります。
小手先でゎない。
混乱を避けるため、EPSはこの関数以外では使わないようにしています。
inline int sgn(Real a, Real b = 0) {return a < b - EPS ? -1 : a > b + EPS ? 1 : 0;} inline bool near(Point a, Point b) {return !sgn(abs(a - b));}
inline Point vec(const Line& a) {return a.b - a.a;}
inline Real arg(const Point& base, const Point& a, const Point& b) {return arg((b - base) / (a - base));}
-EPSを突っ込んで死ぬのを回避。
inline Real sr(Real a) {return sqrt(max(a, (Real)0));}
円と線分をグラフに落とすときにc.c+polar(c.r, PI/2*i)を頂点に追加しておくと便利なことがあります。
円周上をPI/2以下しか動かないのでどっちから来たか簡単に分かります。
どんな面積でも簡単に求められることで有名。
というのはさすが冗談で、例えばサブミットデバッグするときに答えが大きくずれているかのチェックができたりします。
