[問題案] 円の和集合の面積

[tozangezan]

(任意) 問題ID: union_of_circles 問題名: Area of union of circles

(任意) 想定アルゴリズム: {名前} (任意) 参考資料: https://docs.google.com/presentation/d/119Ve9FB0qTzN01P4EKmia-atXMiPSsJGEDWotVZ6GDg/edit?usp=sharing

問題概要

中心(x_i,y_i)半径r_iのN個の円が与えられる。これらの円の1個以上の内部または周上に含まれる領域の面積を求めよ。

入力

N
x_1 y_1 r_1
:
x_N y_N r_N

出力

S

S: 面積

制約

N ≤ 2000

O(N^3) 平面走査: 落としたい O(N^2 log N): 通したい

[tozangezan]

いや今調べたらすでにここにあったわ https://www.algospot.com/judge/problem/read/CIRCLES わざわざyosupoジャッジにも追加する必要あるか？要議論

[yosupo06]

問題と解法の雰囲気を確認しました、他のジャッジにあってもLibrary Checkerっぽい問題なので追加するのは構わないんですが、誤差問題は初めてなのでそれをどうするかですね