TopCoder

Thumb fhvirus icon.001
FHVirus
"FHVirus 是一種由主要由IO組合而成的病毒。"

User's AC Ratio

76.5% (39/51)

Submission's AC Ratio

29.5% (61/207)

Description

數學課上,三葉與瀧正在教導三葉的妹妹四葉如何用圓規:他們標出了$N$個點於座標平面上(第$i$個點為$P_i(x_i,y_i)$,$1 \leq i \leq N$),然後三葉和瀧會分別選擇一個點$P_i$和$P_j$($i \not= j$)然後四葉就會拿著她的圓規以$\overline{P_iP_j}$為直徑畫一個圓。在這個練習結束後,瀧看著畫完的紙張思考——如果知道了每一個點的座標,那他們倆所有可能的選擇畫出來的圓的面積和為何?換句話說,定義$C(i, j)$為以$P_i$、$P_j$所定義出來的圓,其面積以 $|C(i,j)|$ 表示,則想要求的是$\sum_{i \not= j} |C(i, j)|$。

Input Format

第一行有一個正整數$N$表示點的個數。
接下來有$N$行,每一行有兩個以空格分隔的整數$x_i, y_i$,表示第$i$個點的座標。
請注意,這些座標並不保證相異。對於所有的測試資料,保證$1 \leq N \leq 5 \times 10^ 5$,且$|x_i|, |y_i| \leq 10^ 9$。

此外,對於佔分$15\%$的測試資料來說,$N \leq 1000$,
對於佔分$15\%$的測試資料來說,$|x_i|, |y_i| \leq 20$
對於佔分$30\%$的測試資料來說,$y_i = 0$。

Output Format

請輸出一個數字$A$代表總面積。如果你的答案和正確答案的相對誤差小於$10^ {-5}$,則會被評測系統所接受。

Sample Input

第一筆測試資料:
2
0 0
2 0
第二筆測試資料:
4
0 0
1 0
0 1
1 1

Sample Output

第一筆測試資料的答案:
6.28318530718
第二筆測試資料的答案:
12.56637061

Hints

若三葉選$(0, 0)$,瀧選$(2, 0)$,則面積$\pi$;若反過來,則面積也是$\pi$,答案為$\pi + \pi \approx 6.28318530718$。

對於第二筆,雖然$C(1, 4)$和$C(2, 3)$相等,但是還是會個別計算哦!

若想要輸出一個型別為double的數字x至小數點後 $9$ 位,則可以用 printf("%.9lf\n", x)

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~5 $N \leq 1000$ 15
2 6~10 $|x_i|, |y_i| \leq 20$ 15
3 11~15 $y_i = 0$ 30
4 0~20 No additional constraints. 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1 4
1 1000 65536 262144 1 4
2 1000 65536 262144 1 4
3 1000 65536 262144 1 4
4 1000 65536 262144 1 4
5 1000 65536 262144 1 4
6 1000 65536 262144 2 4
7 1000 65536 262144 2 4
8 1000 65536 262144 2 4
9 1000 65536 262144 2 4
10 1000 65536 262144 2 4
11 1000 65536 262144 3 4
12 1000 65536 262144 3 4
13 1000 65536 262144 3 4
14 1000 65536 262144 3 4
15 1000 65536 262144 3 4
16 1000 65536 262144 4
17 1000 65536 262144 4
18 1000 65536 262144 4
19 1000 65536 262144 4
20 1000 65536 262144 4