11515 - Cranes

起重機對於建造大樓是一個很有力的工具，工地上有愈多起重機則施工的速度會愈快，但是愈多起重機卻也增加潛在的危險性，當一台起重機在旋轉的時候，也許一個不小心就會撞到另一台起重機，甚至於導致起重機翻覆，這是一種極危險的情況。為了避免這種潛在的危險，我們規定所有起重機必須離得夠遠，使彼此之間不可能產生碰撞或接觸。這項工作規定限制了工地上起重機的數量，也限制了施工的速度。

工地上會標示起重機可以被放置的位置及該位置上起重機可活動的範圍 r，起重機可以在以 r 為半徑的圓內自由轉動。本題你請在遵守工作規定的情況下放置起重機，並使得所有被放置的起重機的活動面積最大化。

Input Specification

輸入資料的第一列有一個整數表示測試資料的組數，每組測試資料的第一列為整數C表示所有起重機可被放置的位置，位置數最多15個，接下來有C列，每列有三個整數 x, y, r，其值介於-10,000 ~ 10,000，(x, y)為起重機的位置，r 為該位置起重機機臂的長度。

Sample Input

1
3
0 0 4
5 0 4
-5 0 4

Output Specification

請對每組測試資料計算最大的起重機活動面積A，並輸出B值使得A = B x π。

Output for Sample Input

32

---

原文出處