回分類題庫
d055: 4.基地台訊號覆蓋
關鍵字: 101年台中區複賽

測資點 : 5 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 75 Times / 50 Users | Submit : 292 Times / 62 Users | Accepted rate : 81%
題目加入時間 : 2013-09-13 13:51

Content: 简体中文

一家無線網路公司正在某村搭建一個WiMAX基地台。村子裡共有n棟房子需要被訊號覆蓋。由於經費的限制,網路公司只能安裝一個基地台。這裡將每棟房子用一個點座標來表示。為了簡化基地台的放置,網路公司將會選擇其中的3棟房子作一個外接圓,然後將基地台放在圓的中心,所有位於這個圓内或者圓的邊界上的房子都將被基地台訊號所覆蓋。網路公司將會隨機選擇村中的3棟房子所形成的外接圓心来搭建基地台,他們想知道在所有可能放置基地台的方案中平均會有多少棟房子被訊號覆蓋。例如,假設共有4棟房子A, B, C, D,它們的位置如下圖:

 

 如果我們選擇ABC或者BCD三個點所形成的外接圓,那麼所有的房子都被訊號覆蓋。如果我們選擇ACD或者ABD,那麼剩下的房子將不會在基地台的訊號覆蓋範圍內。因此平均有 (4+4+3+3)/4=3.50 棟房子被訊號覆蓋。給定所有房子的位置,你的任務是計算平均有多少棟房子被訊號覆蓋。假定每一棟房子都有一個二维的整數座標,並且保證任何三棟房子都不在同一條直線上,任何四棟房子都不在同一個圓上。

提示:

三角形的外心至三頂點的距離等長,假設外心的座標為(x, y),三角形三頂點的座標分別為(xa, ya)、(xb, yb)、(xc, yc),則三角形的外心公式如下: 

x = △x/△, y = △y/△,其中:
△ = 2(xa-xb)(yc-yb)-2(ya-yb)(xc-xb)
x = (yc-yb)(xa2+ya2-xb2-yb2)-(ya-yb)(xc2+yc2-xb2-yb2)
y = (xa-xb)(xc2+yc2-xb2-yb2)-(xc-xb)(xa2+ya2-xb2-yb2

Input:

輸入資料第一行包含一個正整數 n (4<=n<=10),表示房子的總數。接下来有n行,分别表示每一棟房子的位置座標,數字與數字間以一個空白做間隔。

Output:

輸出一個實數(至小數點後6位),表示平均有多少棟房子被訊號覆蓋。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
4
0 2
4 4
0 0
2 0

Sample Output :

3.500000

Hint :

註1:請注意浮點數誤差。

註2:所給的測資不會有三點共線的情形,但會有四點共圓的情形。

Author :

101年台中區複賽 (管理員:sagit)

  Solve it!   Status Forum