台灣最大程式設計社群網站
線上人數
1975
 
會員總數:244573
討論主題:188713
歡迎您免費加入會員
討論區列表 >> C/C++ >> 形成三角形的周長期望值
[]  
[我要回覆]
1
回應主題 加入我的關注話題 檢舉此篇討論 將提問者加入個人黑名單
形成三角形的周長期望值
價值 : 15 QP  點閱數:273 回應數:2

樓主

cyatmirror
門外漢
0 3
28 5
發送站內信

捐贈 VP 給 cyatmirror
題目如下:
在一個二維平面上,有 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
輸出一行,包含一個浮點數,即為形成三角形的周長期望值。
如果你的答案的絕對或相對誤差不超過 10^6 都會被當作正確。

Sample Input 1
4
0 0
1 0
1 1
0 2
Sample Output 1
4.532247551

以下是我的程式碼:


但是上傳程式碼後的結果是錯誤 而且時間也超過1s的要求
請問我的程式碼哪裡有問題或該如何修改?

搜尋相關Tags的文章: [ npsc ] , [ 三角形 ] ,
本篇文章發表於2018-11-24 16:17
別忘捐VP感謝幫助你的人 新手會員瞧一瞧
1樓
最有價值解答

淺水員
檢舉此回應
C語言中,整數*整數會用整數處理
所以
x=(x1-x2)*(x1-x2);
很容易造成溢位
你可以試試看這段程式碼:

本篇文章回覆於2018-12-02 00:16
== 簽名檔 ==
--未登入的會員無法查看對方簽名檔--
2樓
回應

淺水員
檢舉此回應
速度方面,在運算上可以換個想法
他既然保證任三點都不在同一直線上
所以有 n 個點的話
任意一條直線可以形成 n-2 個三角形
因此任一條直線會被加 n-2 次

由上面的討論
我們只要計算:
(所有相異直線的總和)×(n-2)÷n
就是答案了
這會比原先方法快很多
本篇文章回覆於2018-12-02 00:23
== 簽名檔 ==
--未登入的會員無法查看對方簽名檔--
   
1

回覆
如要回應,請先登入.