#UVa:10784-Diagonal

灆洢 2019-04-03 09:20:08

多邊形的對角線公式為 \( \frac{(n-3) \times n}{2} \),公式的原因是每個點都可以與除了自己與相鄰兩點進行對角線連線,所以會是 \( (n-3) \times n \),但因為兩兩會重複,所以要再除以 2 。

接著主要要求的是在有總數的情況下, n 是多少,也就是這個方程式 \( \frac{(n-3) \times n}{2} = N \),利用二次方程式的公式解,可以得到 \( N = \lceil \frac{3 + \sqrt{9 + 8 \times N}}{2} \rceil \),即可得解。

P.S. 此題數字必須使用 64 位元整數儲存,已經超過了 32 位元整數能儲存的範圍。

C++(0.000)

/*******************************************************/
/* UVa 10784 Diagonal                                  */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2019/04/03                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main(){
  long long int N;
  int caseNumber = 1;
  while(scanf("%lld", &N) != EOF && N != 0){
    long long int sideCount = (long long int)ceil((3 + sqrt(9 + 8 * N)) / 2);
    printf("Case %d: %lld\n", caseNumber++, sideCount);
  }
  return 0;
}

在〈“#UVa:10784-Diagonal”〉中有 1 則留言

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料