算法題解：Viva Confetti 彩紙可見性判斷——平面幾何與遞歸遮擋關係

問題描述

給定 n 個圓盤（彩紙），按疊放順序從底到上列出（第一個最底），每個圓盤由圓心坐標 (x, y) 和半徑 r 定義。從頂部觀察，判斷有多少圓盤至少有一部分可見（不被上方圓盤完全覆蓋）。

輸入輸出

• 多組測試用例，每組第一行 n (≤100)，隨後 n 行 x y r。
• 坐標在 [-10, 10]，精度 1e-12。
• 輸出每組可見圓盤數量。

算法思路

遞歸/迭代檢查遮擋關係：

1. 從最頂層圓盤開始，標記為可見。
2. 對於每個下層圓盤，檢查是否被任意已標記可見的上層圓盤完全覆蓋。
3. 圓盤 A 完全覆蓋圓盤 B 的充要條件：dist(center_A, center_B) + r_B <= r_A（即 B 在 A 內部且不相交邊界）。
4. 若無上層可見圓盤完全覆蓋它，則它可見，加入可見集合。

複雜度

• n ≤ 100，O(n²) 兩層循環完全可接受。
• 精度處理：使用 double，比較時允許 1e-12 容差。

樣例解析

輸入:
3
0 0 0.5
-0.9 0 1.00000000001
0.9 0 1.00000000001
輸出: 3
解析: 底部小圓半徑 0.5，兩側大圓半徑略大於 1，中心距 0.9，大圓無法完全覆蓋小圓，三者皆可見。

參考實現

C++/Java 均可輕松實現，關鍵是幾何判斷函數 bool covers(Circle upper, Circle lower)。

相關鏈接

博客詳細解析：Viva Confetti 題解