Segment Tree - Algoogle
N := 区間の幅 解説 Segment Treeは主に区間に対するクエリを処理するために使われる. 完全二分木で実装されるので各クエリの計算量はO(log N)になる. 自由度が高く, 区間を扱う様々なものに利用される. コードはRMQとその区間足し込みバージョンの実装. この2つの書き方をなんとなくイメージできればある程度柔軟に実装できるようになるでしょう. 区間足し込みはその区間全体に一気に足された数というのを遅延評価することで実現できる. コード struct segtree { int N, dat[2*MAX]; segtree() {} segtree(int n) { N = 1; while(N < n) N *= 2; for(int i = 0; i < 2*N-1; i++) dat[i] = inf; } // update k th element void u
プログラミングコンテストでのデータ構造
2. 内容 • Union-Find 木 • バケット法と平方分割 • セグメント木 • 共通点：自分で実装するデータ構造 • セグメント木が中心 – IOI でのセグメント木の出題が非常に多い
平面幾何におけるベクトル演算
ここでは，ACM/ICPC頻出の平面幾何について，基本的なベクトル演算を解説します。 最後にライブラリとしてソースコードを載せているので本番では印刷して持っておくとよいでしょう。 ベクトルの基礎 デカルト座標系とユークリッド空間 スカラーとベクトル 点とベクトル ベクトルの和と差 ベクトルの利用 complex型の導入 絶対値，2点間の距離，単位ベクトル 法線ベクトル，単位法線ベクトル 内積と外積 内積・外積 2直線の直交判定・平行判定 点が線上にあるかないかの判定 直線と線分 直線と点の距離 線分と点の距離 線分の交差判定 線分の交点計算 直線の交点計算 ソースコード $Id: index.shtml 1825 2007-09-23 00:35:10Z SYSTEM $
幾何学・CG のアルゴリズム集
作成中 スマートフォン (Android，iPhone) など最近のモバイル機器には３軸地磁気センサ (電子コンパス) と３軸加速度センサ (モーションセンサ) を搭載しているものがある．これらを用いると，基準となる３方向 (水平磁北方向，水平東方向，鉛直方向) をそれなりの精度で求めることができ， さらにその結果を用いて端末の姿勢 (向いている方向) や方位角 (azimuth)， 傾き角 (roll，pitch) を計算することができる． 余談だが，Android のマニュアルにある azimuth の定義はおかしい (はっきり言って間違っている) のでセンサアプリ開発者は注意． この定義によると水平面に対する画面の傾きが大きくなるほど azimuth の誤差が大きくなり，画面を垂直にすると全く方位とは無関係な値になる． 実際，ストリートビューに定義どおりの azimuth を渡した場
リアルな映像を作るグラフィックス・アルゴリズム
3次元コンピュータ・グラフィックス（3DCG）の世界で，リアリティは非常に重要なテーマです。リアルな3DCGを作るため，これまで様々な研究/開発がなされ，その成果は映画やビデオ・ゲームなどで誰でも目にすることができるようになっています。そして，現在でもさらなるリアリティの追求のため，日々研究や開発が続けられています。このパートでは，そうしたリアルな3DCGの裏側にある技術の一端をお見せします。 3DCGのリアリティは「形状」「色/質感」「動作」という三つの要素に分けて考えることができます。これらが技術的にどのような難しい点を含んでおり，どのように解決されてきたかは，最後のカコミ記事「3DCGのリアリティを実現する三つの要素」を参照していただくとして，これらの三要素が一定の水準に達したところで浮かび上がってきた，ある問題に焦点を合わせてみましょう。それは自然な動作の大量生成が難しい，という問
グラフィック系アルゴリズムに役立つ「計算幾何学」の入門用ノートPDF （Computational Geometry） - 主に言語とシステム開発に関して
講義ノートの目次へ CGやゲーム開発にも役立つ計算・幾何学（けいさん・きかがく）の教科書。 点・線分などの図形を数値計算する時に必要なアルゴリズムを勉強できる。 プログラミングにすごく役立つ。 複雑な図形どうしの関係を，三角形や木構造を使ってシンプルに考えられるようになり面白い。 たとえば… 平面上に，たくさんの点が存在する。点の分布にしたがって領域を分割し，境界線を描画したい。勢力図やテリトリーを生成したい。（＝ボロノイ図） 複雑な形の部屋で，監視カメラで全体を見渡す。部屋中をもれなく監視するには，どこにいくつカメラを置けばいいか？（＝美術館問題，領域の三角形分割） 地図上で，川が国境をまたぐのはどこ？（＝線分の交差問題） 点とエリアの「当たり判定」をしたい。地図上の１点を選んだとき，その点がどの国に属するのかを高速に求めたい（＝点位置決定問題） 平面上に，たくさんの点が存在する。すべて
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
