1747 . [APIO '10] Signaling [Interactive]
TopCoder
Tags
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 1
0 2
4 4
0 0
2 0
Sample Output 1
以下幾組都是可以被接受的回報：
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 |