回分類題庫
z077: E.三角形
關鍵字: 2018NPSC高中組初賽

測資點 : 10 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 0 Times / 0 Users | Submit : 87 Times / 23 Users | Accepted rate : 0%
題目加入時間 : 2019-10-05 15:25

Content: 简体中文

在一個二維平面上,有N 個點,保證這些點當中任取三個點皆不共線。從這N 個點中任意選取三個相異的點,必定可以形成一個三角形。
 
請問:從這N 個點中均勻隨機的選取三個相異點,所形成三角形的周⻑期望值是多少?
 
以Sample Input 1 為例,從四個點(0; 0)、(1; 0)、(1; 1)、(0; 2) 中,取三個相異點的方法
總共有4 種:
 
• 選取(0; 0)、(1; 0)、(1; 1):得到周⻑約為3:41421356 的三角形
• 選取(0; 0)、(1; 0)、(0; 2):得到周⻑約為5:23606798 的三角形
• 選取(0; 0)、(1; 1)、(0; 2):得到周⻑約為4:82842712 的三角形
• 選取(1; 0)、(1; 1)、(0; 2):得到周⻑約為4:65028154 的三角形
 
將這4 種方法得到的三角形周⻑取平均後(相加再除以4),得到答案約為4:53224755。

Input:

測試資料第一行包含一個正整數N,表示平面上有N 個點。接下來N 行,每行包含兩個
正整數Xi; Yi,表示第一個點的座標為(Xi; Yi)。
• 3<=N<=2000
• -10^9<=Xi; Yi<=10^9
• 保證N 個點中,任三點不共線

Output:

1.輸出一行,包含一個浮點數,即為形成三角形的周⻑期望值。
2.如果你的答案的絕對或相對誤差不超過10^(-6) 都會被當作正確。

Sample Input:help

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

Sample Output :

4.5322475511

Hint :

Author :

2018NPSC高中組初賽 (管理員:jasminshuang)

  Solve it!   Status Forum