# TTPC2023 D

サブミット
https://atcoder.jp/contests/ttpc2023/submissions/46825607

## 問題の言い換え(雑バージョン)

多分公式解説と同じ

ある点iが見えない領域を考えます。これは円錐のような形をしています。
原点から距離 r と距離 r' (>r) の球面を考えると、この球面上で円錐は円を描きます。
この円のサイズは距離 r' の方が小さくなります。(証明略)
つまり、距離 r の球面で連結な領域は距離 r' でも連結です。
また距離 r と距離 r+Δ を考えれば、この2つの球面間も連結になります。
ということで、結局無限遠の球面だけ考えれば良くなります。

無限遠の球面での円のサイズですが、直感的には無限遠からすれば原点と点iは同一視出来るので、「点iから宇宙船の接線の角度」を保ったまま、点iのかわりに原点を頂点にする円錐とみなせます。(証明略; 多分ε-δとか)
ということで、(無限遠ではもはや距離は意味を成さないので)この角度を半径として持てば言い換え完了です。

最終的に、この円で切り取った時に球面がどれだけ残るか？という問題になりました。

## 残った面の数え上げ

公式解説は半平面とか言ってて怖いんですが、普通に球面上のグラフ問題に落とします。

まず他の円に完全に包含された円を削除します。O(N^2)

交差して連結している円の集合体を考えます(球面上に留意)。
円の交点を点とし、交点と交点を結ぶ弧を辺とみなし、各辺が「何個の他の円に含まれているか」を数えます。これは普通に円の交差を計算して点を追加して、円の循環に気をつけてimos法をすれば良いです。ソートが重くてO(N^2logN)
このようにするとカウントが0の辺は「円の集合体の内部と外部を切る辺」なので、この辺と点でUFして「外部と内部の隣接数」が数えられます。

あとは円自体の連結成分数と、上記で求めた「外部と内部の隣接数」をうまく足し引きすれば答えが出ます。

### おまけ: 球面幾何

* 球面の半径を1とすると球面上の距離はラジアン角に一致する
* 球面上に書いた円はある平面上に乗る
* 中心点P(球面上)を、OPに垂直な適当なベクトルを軸に半径分回転させると円上に乗る
* これをOPを軸に適当に2回回転させれば円上の3点が取れるので平面の法線が求まる
* 回転を 2pi/3 ずつにすれば重心が平面上の円の中心になって便利
* 球面上に書いた円と円の交点は、その平面と平面の交線上に乗る
* なので平面に落としたら2D幾何が出来る
* 後で3Dに戻してもう片方の円との整合性を取る必要があるので注意(もう片方の円と時計回り・反時計回りの向きが同じとは限らない……かもしれないので)