Problem : 238 - Signaling

Special Judge

Problem Statistics

Solved Member: 7　　Submission: 58　　User Tried: 7

Statement:

一家電信公司正在北京市發展GSM網路。這個城市中有n個房子需要被網路所覆蓋。因為經費限制，該公司只能安裝一條天線。
為了簡化天線的設置，必須先挑選3間房子畫成一個圈圈，然後將天線設置在該圈圈的中心點。
天線的範圍將會是所有房子都落在圈圈內，包含圈圈邊界上的房子都將被覆蓋。

這家公司計畫隨機挑選3間房子，所以他們想要計算在天線所設置的可能位置上，即將被覆蓋的房子間的平均數。

舉例來說，假設有4間房子A, B, C和D，所在位置如下圖所示。

如果我們選擇圈圈是ABC或BCD所串連，每個房子都將被覆蓋著。
但如果我們選擇圈圈是ACD或ABD所串連，第四間房子將無法被天線的範圍所覆蓋。
因此，將被覆蓋房子的平均數為 (4 + 4 + 3 + 3) /4= 3.50。

你的任務就是計算被信號覆蓋的房子平均數及假設房子位置。
房子的位置將依據二維座標系統讓所有房子都有其座標。
你要確保沒有三間房子會落在同一條線上，也沒有四間房子會落在同一個圈圈裡。

Input:Output:

輸入的第一列包含一個正整數 n，也就是房子的總數。

接下來有 n 列，描述著房子的位置。當 i ∈ {1, 2, ... , n}，房子i的座標是一對整數x_i 和 y_i 在輸出的i+1列上，由空格間隔開來。

•在 100% 的測試案例中，房子i的座標 (xi, yi)都是整數，也就是 -1000000 ≦ xi, yi ≦ 1000000
•沒有三間房子會落在同一條線上，也沒有四間房子會落在同一個圈圈裡。
•在 40% 的測試案例中， n ≦ 100
•在 70% 的測試案例中， n ≦ 500
•在 100% 的測試案例中，3 ≦ n ≦ 1500

輸出必須包含一個單一實數，讓房子的平均數都能被信號所覆蓋。結果的絕對誤差必須少於或等於0.01。

Sample Input:Sample Output:

4
0 2
4 4
0 0
2 0

3.5000

Source:

APIO 2010

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	2000ms	65536kb
1	2000ms	65536kb	10
2	2000ms	65536kb	10
3	2000ms	65536kb	10
4	2000ms	65536kb	10
5	3500ms	65536kb	10
6	3500ms	65536kb	10
7	3500ms	65536kb	10
8	3500ms	65536kb	10
9	3500ms	65536kb	10
10	3500ms	65536kb	10