円と円の交点
AtCoder
ABC-F
AtCoder600点
計算幾何
最適化テク:端点のみを考える
最適化テク:解を変形していく(最適性を失わずに)
二分探索
アポロニウスの円
円と円の交点
二次元平面上のN点の問題
最適化テク:制約条件を加えて探索候補を絞る
N個からK個を選ぶ設定の問題
橙色diff
最小回数・最小個数を求める
所要時間を求める問題
最適化問題
浮動小数点型を扱う問題
ABC 151 F 以来の幾何ですね。ABC 151 F の解法のうち「探索候補として交点を考える」というのが今回もいい感じに使える! drken1215.hatenablog.com 問題へのリンク 問題概要 二次元平面上に 個の点 が与えられる。それぞれの点に肉が置いてある。このうち…
円と多角形の共通部分の面積を求めるライブラリ、一念発起して整備した!!! サブルーチンとして「円と "線分" の交点を求める」というライブラリが必要となる。 問題へのリンク 問題概要 原点を中心とした半径 の円と、 頂点の多角形が与えられる。これら…
円と円の共通部分の面積!!! 問題へのリンク 問題概要 円が 2 つ与えられる。それらの共通部分の面積を求めよ。 制約 座標の絶対値が 以下 解法 「接する場合」を除くと、以下の 3 パターンにわかれる 完全に disjoint (面積は 0) 2 点で交わる 一方が他方…