スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

角度がとても小さくなる

幾何問題 (UVa 12226) を解いているときにちょっとはまったので記録しておく。

Tag : アルゴリズム

この問題を解くために、点集合を ( ある定点からの偏角, 定点からの距離 ) の辞書順でソートした。
比較関数はこんな感じ。
bool cmp_arg(const point &a,const point &b){
double ta=arg(a);
double tb=arg(b);
return ta+EPS<tb || abs(ta-tb)<EPS && abs(a)<abs(b);
}

問題の設定では、座標値は整数で絶対値 10^4 以下。
値がそれほど大きくないので、なんとなく EPS=1e-8 くらいで大丈夫だろうと思っていた。

次のような入力を考えてみる。 ( これに似た入力が実際のジャッジデータにもある )

A を定点として B, C, D をソートすると、C, D, B という順になるはず。
ところが、実際は C, B, D という順になってしまう。
問題は ∠DAB が小さすぎること。
このために B と D の偏角が等しいと判定されて、その結果、A に近い B が前に来てしまう。

∠DAB はどれくらい小さいのか?
θ ≒ sinθ の近似を使っておおざっぱに計算すると、∠DAB は座標値の逆数の二乗のオーダーになる。
この場合、大体 10^-8 程度。
ちなみに、厳密な値は double の精度で 5.000750037494257e-09 [rad] となる。

なので、EPS=1e-8 と選ぶと間違う。
角度は意外と(?)小さくできるので誤差には十分注意しましょう、という教訓を得た。

今回は EPS をさらに小さくして通したけど、座標値がもっと大きくなったら対応できない。
本当は、角度を明示的に求めなくても整数演算だけで cmp_arg を書くことはできる。やっぱり整数だけでできるところは整数でやったほうがいいと改めて思った。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。