宇宙船、つまり原点を中心とする半径 \(R\) の球を \(B\) とします。 \(P_i\) を端点に持つ半直線であって \(B\) に接するものによって囲まれた領域を考えると、その形状は \(P_i\) を頂点とする円錐になっています。この円錐を頂点が原点 \(O\) になるように平行移動させたものを \(\lambda_i\) とします。また、平行移動する前の円錐を、その円錐と球面の交面で切って \(P_i\) を含まない側を残した領域を \(\Lambda_i\) とすれば、これは \(i\) 番目の星を見ることができない領域に一致しています。

ただし、図形は \(\mathbb{R}^3\) 上の点の集合として考えます。また \(\lambda_i,\Lambda_i\) はその境界を含みます。

本問題は、原点を中心とする半径 \(1\) の球面 を \(S\) としたとき、 \(S\setminus\bigcup_i\lambda_i\) がいくつの領域に分かれているかを求める問題です。

この帰着は自明ではないので、証明を記します。

\(S\) と \(\lambda_i\) の交線は円になります。上の図は、サンプルの 1 つめのテストケースにおいてそれらの円と \(S\) を表示したものです。

次に帰着後の問題を注意深く観察します。球面上にいくつかの円が描かれているとき、そのすべての外側にある球面上の領域がいくつあるか、という問題になっています。ここで、球面上に描かれたそれらの円は、それぞれある平面上に乗っていることに注目し、次のように言い換えます。

球面 \(S\) をいくつかの平面で切断し、平面に対して原点と同じ側の部分だけ残したとき、いくつの領域に分かれるか。

ここで \(S\) と \(\lambda_i\) の交面との境界となる円を含む平面を \(\sigma _i\) とし、 \(\sigma _i\) に対して原点側の半空間を \(H_i\) とします。そして \(i=1,2,\dots ,N\) に対する半空間 \(H_i\) の積(halfspace intersection)としての凸包 \(C\) を考えます。このとき \(S\cap C\) がいくつの領域に分かれているかを求めたいです。

必要ならば \(S\) を完全に含むような半空間をさらにいくつか追加することで \(C\) は有限の領域に収まっているとします。 \(S\cap C\) は特に \(C\) の内側の領域で、逆に言えば球面の外側に \(C\) の一部が存在することになります。このことに注目して、凸包によって切り取られた球ではなくて、逆に球によって切り取られた凸包に焦点を当ててみましょう。つまり \(C\) のうち原点からの距離が \(1\) より大きな部分 ( \(=C^\prime\) ) がいくつの領域に分かれているかを求めることができれば、それが元の問題の答えになっています。

\(C\) 上の点であって原点からの距離が極大となる点は \(C\) の頂点のみであることから、異なる \(2\) 頂点が同じ領域にあるためには \(C^\prime\) 上の \(C\) の辺を辿って行き来可能であることが必要十分です。以上の考察から次の解法が得られます。

• \(i=1,2,\dots ,N\) に対して平面 \(\sigma_i\) を計算し、それにより定まる半空間 \(H_i\) たちの積としての凸包 \(C\) を計算する。
• 必要ならば \(S\) を完全に含む半空間をいくつか追加して \(C\) を有限にする。
• \(C\) のうち原点からの距離が \(1\) より大きな点および辺からなるグラフの連結成分の個数を答える。

半空間の積としての凸包を計算するアルゴリズムはいくつか知られていますが、例えば平面を \(N\) 通り全て調べ、その平面上での半平面の積(halfplane intersection)を偏角ソートを用いて \(O(N\log N)\) 時間で計算する方法によって、 \(1\) ケースあたり \(O(N^2\log N)\) の時間計算量で凸包を計算することができます。辺および頂点の個数は \(O(N)\) であることから、連結成分の個数を求めるパートは UnionFind などを用いればボトルネックになることはありません。