幾何の基本判定・配置・座標変換
交差・方向・距離・接触条件を、外積、端点順、格子占有または変換後座標の局所判定にする。
この典型を扱う単元: 幾何の基本判定と座標変換
検索別名: Manhattan transform、computational geometry、外積判定、計算幾何
未知問からこの典型を見つける手掛かり
- 扱う対象
- 座標
- 弦
- 点
- 直線
- 立方体
- 線分
- 距離
- 面
- 使う手掛かり
- 交差
- 回転
- 左側
- 幾何
- 接触
- 方向
- 端点順
- 保つ不変量
- cross
- x-y
- x\+y
- 六近傍
- 端点の交互性
- 符号
- 求めるもの
- 交点
- 判定
- 移動コスト
- 距離
- 隣接面
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 幾何・凸最適化への変換
関連する典型
学習成果と学習単位
幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。
幾何の基本判定と座標変換で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC223 E「Placing Rectangles」 公式問題主題: 幾何の基本判定と座標変換 / 主タグ
- ABC351 E「Jump Distance Sum」 公式問題主題: 幾何の基本判定と座標変換 / 主タグ
- ABC220 G「Isosceles Trapezium」 公式問題主題: 幾何の基本判定と座標変換 / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC220 G「Isosceles Trapezium」 公式問題主題: 幾何の基本判定と座標変換 / 主タグ
- ABC221 G「Jumping sequence」 公式問題主題: bitsetで集合演算をword並列化する / 補助タグ
- ABC223 E「Placing Rectangles」 公式問題主題: 幾何の基本判定と座標変換 / 主タグ
- ABC225 E「7」 公式問題主題: 交換論から選択順を導く / 補助タグ
- ABC233 Ex「Manhattan Christmas Tree」 公式問題主題: parallel binary search・多数境界の判定共有 / 補助タグ
- ABC234 Ex「Enumerate Pairs」 公式問題主題: 幾何の基本判定と座標変換 / 主タグ
- ABC240 G「Teleporting Takahashi」 公式問題主題: 組合せ係数と対称性で数える / 補助タグ
- ABC243 Ex「Builder Takahashi (Enhanced version)」 公式問題主題: 最短路モデル / 補助タグ
- ABC248 E「K-colinear Line」 公式問題主題: 幾何の基本判定と座標変換 / 主タグ
- ABC250 F「One Fourth」 公式問題主題: 尺取り法・sliding windowで連続区間を走査する / 補助タグ
- ABC258 F「Main Street」 公式問題主題: 幾何の基本判定と座標変換 / 主タグ
- ABC263 Ex「Intersection 2」 公式問題主題: 単調境界を証明して探索する / 補助タグ
技能・出典
主題: 単調境界を証明して探索する
主タグ: 単調境界探索 / 補助タグ: 円環順序・chord交差、event・値順のオフライン走査、Fenwick Tree・反転数・重み付き接頭辞統計、幾何の基本判定・配置・座標変換
- ABC266 Ex「Snuke Panic (2D)」 公式問題主題: event順にactive集合を更新する / 補助タグ
- ABC274 F「Fishing」 公式問題主題: event順にactive集合を更新する / 補助タグ
- ABC280 G「Do Use Hexagon Grid 2」 公式問題主題: 包除・Möbius反転で重複を補正する / 主タグ
- ABC283 F「Permutation Distance」 公式問題主題: event順にactive集合を更新する / 補助タグ
- ABC296 G「Polygon and Points」 公式問題主題: 幾何の基本判定と座標変換 / 主タグ
- ABC301 G「Worst Picture」 公式問題主題: 幾何の基本判定と座標変換 / 主タグ
- ABC314 Ex「Disk and Segments」 公式問題主題: 一次元凸・単峰最適化 / 補助タグ
- ABC315 F「Shortcuts」 公式問題主題: 列・subsequence DP / 補助タグ
- ABC323 F「Push and Carry」 公式問題主題: 同値な状態を正規化する / 補助タグ
- ABC343 E「7x7x7」 公式問題主題: 候補数を界して全列挙・有限case分解する / 補助タグ
- ABC351 E「Jump Distance Sum」 公式問題主題: 幾何の基本判定と座標変換 / 主タグ
- ABC353 F「Tile Distance」 公式問題主題: 幾何の基本判定と座標変換 / 主タグ
- ABC366 E「Manhattan Multifocal Ellipse」 公式問題主題: 幾何の基本判定と座標変換 / 主タグ
- ABC377 F「Avoid Queen Attack」 公式問題主題: 幾何の基本判定と座標変換 / 主タグ
- ABC385 F「Visible Buildings」 公式問題主題: 幾何の基本判定と座標変換 / 主タグ
- ABC410 G「Longest Chord Chain」 公式問題主題: 値域集約による部分列DP / 補助タグ
- ABC418 E「Trapezium」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC422 E「Colinear」 公式問題主題: 乱択の成功条件と誤り確率を設計する / 補助タグ
- ABC426 E「Closest Moment」 公式問題主題: 幾何の基本判定と座標変換 / 主タグ
- ABC437 F「Manhattan Christmas Tree 2」 公式問題主題: 幾何の基本判定と座標変換 / 主タグ
- ABC442 E「Laser Takahashi」 公式問題主題: 幾何の基本判定と座標変換 / 主タグ
- ABC457 G「Catch All Apples」 公式問題主題: 半順序・Dilworth・最大反鎖 / 補助タグ