2167 . 君のコンパスは。

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

77.0% (77/100)

Submission's AC Ratio

22.3% (107/480)

Tags

CKcon 2020-CKcon

Description

數學課上，三葉與瀧正在教導三葉的妹妹四葉如何用圓規：他們標出了N個點於座標平面上（第i個點為Pi(xi,yi)，1≤i≤N），然後三葉和瀧會分別選擇一個點Pi和Pj（i≠j）然後四葉就會拿著她的圓規以PiPj―為直徑畫一個圓。在這個練習結束後，瀧看著畫完的紙張思考——如果知道了每一個點的座標，那他們倆所有可能的選擇畫出來的圓的面積和為何？換句話說，定義C(i,j)為以Pi、Pj所定義出來的圓，其面積以 |C(i,j)| 表示，則想要求的是∑i≠j|C(i,j)|。

Input Format

第一行有一個正整數N表示點的個數。
接下來有N行，每一行有兩個以空格分隔的整數xi,yi，表示第i個點的座標。
請注意，這些座標並不保證相異。對於所有的測試資料，保證1≤N≤5×105，且|xi|,|yi|≤109。

此外，對於佔分15%的測試資料來說，N≤1000，
對於佔分15%的測試資料來說，|xi|,|yi|≤20
對於佔分30%的測試資料來說，yi=0。

Output Format

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

Sample Input 1

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

Sample Output 1

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

Hints

若三葉選(0,0)，瀧選(2,0)，則面積π；若反過來，則面積也是π，答案為π+π≈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≤1000 15
2 6~10 |xi|,|yi|≤20 15
3 11~15 yi=0 30
4 0~20 No additional constraints. 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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
Submit
Back to Top