![]() ![]() ![]() ![]() |
|||||
|
|||||
樓主 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的要求 請問我的程式碼哪裡有問題或該如何修改? |
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
== 簽名檔 ==
--未登入的會員無法查看對方簽名檔-- |
回覆 |
如要回應,請先登入. |