[]
[我要回覆]
1
|
|||||
|
|||||
樓主 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的要求 請問我的程式碼哪裡有問題或該如何修改? |
||||
0
3
28
5
| 別忘捐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
| 回覆 |
| 如要回應,請先登入. |
