TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

58.8% (10/17)

Tags

Description

  在遠古時期,NPSC 大陸的社會主要以封建制度為主,因此整個大陸上有許多領主,各自有自己的領地。

  當然,領主會希望自己的領地愈大愈好,所以不同領主間會有領地上的衝突。也因此,各領主需要有自己的軍隊來保護自己的領地。然而,因為運輸系統不發達,領主的軍隊在沒有需要打仗的時候必須駐守在領主的大本營,才能有充足的糧食供應。又因為那個時代還沒有遠距離武器,因此從大本營到戰場的距離便成了領主是否能獲得勝利的關鍵。

  過了幾年之後,領主們發現一直打仗實在是太勞⺠傷財了,又沒有辦法獲得太多實質的利益,於是決定互相簽訂合約劃分領地。領地劃分的原則很簡單:對於某一片土地,如果它到某個領主 $i$ 大本營的直線距離比到其他所有領主大本營的直線距離都短,那這片土地就算是領主 $i$ 的領地。

  然而,領主們想要知道這樣一劃分下來,他們能分得的領地面積有多少。然而,他們不太會算數學,所以請你幫忙由這 $N$ 個領主的大本營位置,計算出每個領主分得的領地面積有多少。為了簡化問題,請你假設 NPSC 大陸是一個無限大的二維平面。

Input Format

輸入的第一行包含一個正整數 $N$,代表總共有幾個領主。

接下來的 $N$ 行中,第 $i$ 行有兩個整數 $x_i, y_i$,代表第 $i$ 個領主大本營位置的座標是 $(x_i, y_i)$。

  • $N\leq 10^ 5$
  • $|x_i|, |y_i| \leq 10^ 8$
  • 任兩個領主的大本營位置都不相同

Output Format

請輸出 $N$ 行,每行包含一個浮點數,第 $i$ 行代表第 $i$ 個領主分得的領地面積。若某個領主的領地面積是無限,則請輸出一行 “$-1$”(不含引號)。

如果某一行的答案是 “$-1$”,則你的輸出必須是 “$-1$” 才會被視為正確;否則,只要你的答案絕對或相對誤差不超過 $10^ {−7}$,即會被視為正確。

Sample Input 1

4
0 0
3 0
0 3
1 1

Sample Output 1

-1
-1
-1
6.000000000000

Sample Input 2

3
0 0
1 1
2 2

Sample Output 2

-1
-1
-1

Hints

Problem Source

2018 網際網路程式設計全國大賽
高中組決賽

Subtasks

No. Testdata Range Score
1 0~14 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 524288 65536 1
1 4000 524288 65536 1
2 4000 524288 65536 1
3 4000 524288 65536 1
4 4000 524288 65536 1
5 4000 524288 65536 1
6 4000 524288 65536 1
7 4000 524288 65536 1
8 4000 524288 65536 1
9 4000 524288 65536 1
10 4000 524288 65536 1
11 4000 524288 65536 1
12 4000 524288 65536 1
13 4000 524288 65536 1
14 4000 524288 65536 1