長方形・中心ページの位置づけ
| 項目 | 内容 |
|---|---|
| 必修度 | 発展 |
| 学習目安 | 発展 |
| 前提 | 座標・浮動小数 |
| 対象問題 | 5問（推定値あり5問、未算出0問） |
この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。
| 学習目安 | difficulty推定値 | 問題数 |
|---|---|---|
| 入門 | difficulty < 0 | 1 |
| 標準 | 0〜799 | 1 |
| 標準〜発展 | 800〜1199 | 1 |
| 発展 | 1200以上 | 2 |
| 未算出 | — | 0 |
対称性や中心点の性質を使い、面積や分割条件を式へ落とします。浮動小数点の扱いも確認します。
問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。
長方形・中心の見分け方
- 中心を通る直線や対称な配置が現れる
- 図形の面積を半分に分ける条件がある
- 整数入力でも答えが小数になる
長方形・中心の実装前チェック
- 中心座標を式で求める
- 境界上の扱いを分ける
- 出力誤差と除算の型を確認する
先に確認する文法・ライブラリ
まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。
代表問題で実装を確認する
最初の一問として、ABC183 B Billiards（公式解説）を解きます。ゴールをx軸の下へ反転すると、2点を結ぶ直線とx軸の交点が答えになります。一次関数の内分比からx座標を求めます。
SX, SY, GX, GY = map(int, input().split())
print((SX * GY + GX * SY) / (SY + GY))式を1回計算するO(1)時間・O(1)メモリです。
長方形・中心の学ぶ順番
このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。
まず解く
| 問題 | 公式解説 | 出題意図 | difficulty |
|---|---|---|---|
| ABC183 B Billiards | 公式解説 | Use the intersection of the ball trajectory with the x-axis to solve a linear interpolation formula. | -55 |
| ABC130 C Rectangle Cutting | 公式解説 | 長方形の中心を通る直線なら二等分になることを利用し、中心点かどうかも判定する。 | 626 |
| ABC197 D Opposite | 公式解説 | Find the polygon center from opposite vertices and rotate the first vertex by 2π/N around it. | 831 |
| ABC139 F Engines | 公式解説 | 進行方向と内積が正になるベクトルは角度順で連続区間になることを使い、倍長配列の区間和を全探索する。 | 2034 |
| ABC207 D Congruence Points | 公式解説 | Anchor one point, try each candidate correspondence, and test whether a common rotation and translation maps all points. | 2074 |
問題文を読んだら、まず「見分け方」のどれに当たるかを一行で記録します。当てはまらない問題は、別のページへ移す判断自体を復習材料にします。
