UVA 10784 - Diagonal

Problem link

Keyword: geometry, finding pattern

Algorithm:

For triangles, we have no diagonals; for quadrangles, we have 2 diagonals; for pentagons, we have 5 diagonals; for hexagons, we have 9 diagonal as the problem statement.
We can see that the difference in the quantity of each polygon is increasing at a stable rate. (2 from 3→4, 3 from 4→5, 4 from 5→6...) Therefore, we can calculate how many diagonals in N-gon easily.
The easiest way is to calculate the quantity of diagonals of each N-gon and use lower_bound(O(lg N) in search and O(N) in construction) algorithm to find the answer, but you may also use some techniques to find the O(1) formula.

Code:

#include<cstdio>
#include<cstdlib>
#include<cmath>

int main()
{
    long long int n, t = 0;

    while( scanf( "%lld", &n ) && n )
        printf( "Case %lld: %.0f\n", ++t, ceil( ( sqrt( n * 8 + 9 ) - 1 ) / 2 ) + 2 );

    return 0;
}