Hatena::Grouptopcoder

not's memo

 | 

2014-12-09

幾何の小手先テクn選

22:18 | はてなブックマーク - 幾何の小手先テクn選 - not's memo

これは、Competitive Programming Advent Calendar Div2014の9日目の記事です。

誤差

typedef double Real;

誤差死したときはlong doubleにし、TLEしたときはdoubleにできるように最初からtypedefしておくと便利です。

EPSゲー

座標の範囲が[-1000:1000]だとEPS=1e-8を使うというのを基準にしていて、相対誤差っぽく[-10000:10000]だとEPS=1e-7とかにすると苦しむことが減ります。

縮退

回転

与えられた全ての点を原点を中心に少しだけ回転させる。

スラブ分割(コンピュータ・ジオメトリ P.149)する時など、x座標が同じ頂点があって縮退している場合に縮退が解けます。

例題:最終防衛線

(x,y)->(x+α*y,y)

上と同じタイプの縮退が解けます。

乱数

座標に小さな乱数(ただしEPSよりは十分大きい)を追加して縮退を解く。

例題:Exportation in Space

ただし、実際に値を出すときは縮退前の座標を使わないとちょっとずれてWAの原因になります。

記号摂動

小手先でゎない。

便利関数

sign

混乱を避けるため、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));}
vec
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));}
sqrt

-EPSを突っ込んで死ぬのを回避。

inline Real sr(Real a) {return sqrt(max(a, (Real)0));}

その他

c.c+polar(c.r, PI/2*i)

円と線分をグラフに落とすときにc.c+polar(c.r, PI/2*i)を頂点に追加しておくと便利なことがあります。

例題:Magnum Tornado

円周上をPI/2以下しか動かないのでどっちから来たか簡単に分かります。

モンテカルロ法

どんな面積でも簡単に求められることで有名。

というのはさすが冗談で、例えばサブミットデバッグするときに答えが大きくずれているかのチェックができたりします。

 |