TopCoder

Thumb 100
tmwilliamlin
我的中文很爛

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

21.7% (5/23)

Description

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

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

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

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

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

Input Format

輸入的第一列包含一個正整數n,也就是房子的總數。
接下來有n列,描述著房子的位置。
當 i ∈ {1, 2, ... , n},房子i的座標是一對整數xi 和 yi 在輸出的i+1列上,由空格間隔開來。

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

Output Format

求出一個實數R,表示平均有多少個房子被信號所覆蓋。

為了方便驗證,請引入#include "lib1747.h

並使用以下函式回報答案:

Report(int x1, double R);
表示"第一棟房子的x座標"跟你的答案R。R的誤差在0.01內都可以被接受。

Sample Input

4
0 2
4 4
0 0
2 0

Sample Output

Report(0, 3.5000);

以下幾組都是可以被接受的回報:
Report(0, 3.49);
Report(0, 3.51);
Report(0, 3.499999);

Hints

Problem Source

原TIOJ1747 / APIO '10

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 4
4 2000 65536 262144 5
5 2000 65536 262144 6
6 2000 65536 262144 7
7 2000 65536 262144 8
8 2000 65536 262144 9
9 2000 65536 262144 10