計算幾何
コンテストページ: AtCoder Beginner Contest 292 - AtCoder コンテスト中AC: A〜D コンテスト後にE,Fを解説ACしました。要点ををまとめておきます。 D - Unicyclic Components Union-Findで連結成分の何らかのデータを統合していく問題はよく出題されます。…
コンテストページ:AtCoder Beginner Contest 275 - AtCoder コンテスト中AC:A,B,D コンテスト後AC:E,F(自力) Cでハマったのと、Eで回数制限があることを忘れて考察してしまいました。 C - Counting Squares D - Yet Another Recursive Function E - Sugoroku…
コンテストページ AtCoder Beginner Contest 266 - AtCoder コンテスト中AC:A,B,D コンテスト後にC,E,Fを自力(AtCoderの解説を見ず)AC C - Convex Quadrilateral 下のサイトに判定方法がありました。 第6回 多角形の幾何(前編) | gihyo.jp 多角形上を半時…
コンテスト中AC:A〜D D - Range Count Query E - K-colinear Line ので管理 ので管理 探索済みの点対を管理 基準となる2点を管理 点が直線上にあるかの判定 D - Range Count Query ウェーブレット行列が使えます。 ウェーブレット行列には以下の関数がありま…
コンテスト中AC:A〜D C - Triangles? で全探索可能です。 面積が正でない三角形は、面積が0の三角形です。 言い換えると、直線上に3点が並んでいる時、面積は0になります。 3点が直線上にある時、線分の傾きが同じになるので、 三角形の面積が0でない時、 が…