TopCoder

User's AC Ratio

74.4% (29/39)

Submission's AC Ratio

34.8% (57/164)

Tags

Description

在當年的大戰之後,黑魔法師黯慄到黑森林中補充魔力,周強也把兵器收了起來,為了尋找不可視境界線而繼續踏上旅程,這個世界恢復了短暫的和平。
在世人們最後一次遇到周強時,周強對世人們說了。
「聯集跟交集只差了兩個圓面積(?」
世界上的人們都為此百思不解,每個專業的物理學家、天文學家、政府機構都為了解出這句話的含義而費盡心思。
每個人都試圖解出其中的奧秘,世界上最強的超級電腦也日夜不停的運算可能的結果。
經過了無數的失敗,進度一愁莫展,在大家準備放棄時,事情突然出現了轉機。
在天龍國發現的圓形巨石陣中,找到了一些盧恩文字,像是在計算某些東西,於是科學家們了解了!
「只要扣掉兩個圓的面積,就可以得到兩個圓的交集面積了!」
妹可聽說了這個振奮的結果非常開心,他馬上到了當年大戰的遺蹟「硬佛石窟」,在裡面,妹可發現了當年黑魔法師黯慄和周強對抗時留下來的魔力爆破痕跡,這些痕跡剛好都是圓形的。
「終於能解出多年來全球暖化的問題了!」
妹可已經透過硬佛石窟中的壁畫和天龍國巨石陣中的盧恩文字推算出可以得到結果的方程式了,現在只要計算出黯慄和周強的魔力覆蓋幅度,也就是兩個圓形重疊的面積,就可以統制世界了。

妹可已經知道周強跟黯慄當時的位置座標,他也知道他們的法力半徑,但是妹可還要跟其他女生用FB聊天,於是想要請你寫個程式幫他算,算完他會請你吃黑糖冰以感謝你的辛勞。

雖然妹可覺得不需要,但是還是順便把他多年來的研究結果給你,以防你遇到困難時可以使用(妹可:「哼,人家...人家才不是因為擔心你所以才幫你的喔!你可以不要用啊!」)。

以下是妹可給你的研究資料:
海龍公式:
$$設三角形的三邊長分別為 a, b, c。\ 三角形面積A = \sqrt{ s(s - a)(s - b)(s - c)},其中 s = {{a+b+c}\over 2}$$

餘弦定理:
$$設三角形的三個角分別為A,B,C,他們的對邊長分別為a,b,c,\ 角A的角度\theta = acos( {b^ 2+c^ 2-a^ 2 \over 2bc} )$$

扇形面積公式:
$$設扇形圓心角角度為 \theta,扇形面積A = {r^ 2\theta \over 2}$$

Input Format

第一行有一個整數T,代表有T組魔力爆破痕跡。
每個魔力爆破痕跡,妹可會給你六個整數x1,y1,r1,x2,y2,r2,分別代表當時周強站在(x1,y1),法力半徑為r1,黯慄站在(x2,y2),法力半徑為r2。

對於33%的測試資料,滿足兩圓不會重疊。
對於66%的測試資料,滿足兩圓沒有交點。
對於100%的測試資料,滿足-1000≤x1,y1,x2,y2≤1000,1≤r1,r2≤1000,1≤T≤104

Output Format

輸出兩人的法力交集面積大小,請四捨五入至小數點後第二位。

Sample Input 1

3
0 0 5 0 7 4
0 0 1 0 0 3
0 0 10 0 20 10

Sample Output 1

7.66
3.14
0.00

Hints

圓周率$\pi$可以透過acos(-1)取得。
可以在#include <cmath>之後,使用acos()sqrt()分別取得acos的值和平方根的值。

Problem Source

果茶
2015建中校內資訊能力競賽

Subtasks

No. Testdata Range Score
1 0 33
2 1 33
3 2 34

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3