Uva 10213.How many pieces of land

Problem: 10213.How many pieces of land

---

Description:

F(N) = ( N * (N-1) * (N*N-5*N+18) / 24 ) + 1
proof:
oh......that is quite difficult to tell you the proof by text......hope you will understand what I say:Let P(n) be the number of lands when n points are drawn on circle…. Now assume knowing P(n-1), want to know P(n) by adding the n-th point

when the n-th point draw a line to the k-th point (1 <= k <= n-1)on the LHS on k-th point, there is k-1 points between k-th and n-th point on the RHS on k-th point, there is (n-1)-k+1 points between k-th and n-th point the points in these 2 sets(LHS, RHS) are completely connected,so there are (k-1)*(n-k) lines crossed by the newly drawn line,creating (k-1)*(n-k)+1 new lands......
So, drawing lines from newly added n-th point to all n-1 old points,
will create summation[(k-1)(j-k)+1] {k = 1..j (j = n-1)} new lands
let says the summation be F(j)
P(n)= P(n-1) + F(n-1)
= P(n-2) + F(n-2) + F(n-1)
.....
= P(0) + F(1) + F(2) + ....... + F(n-1)
= 1 + summation(F(i)) {i = 1..n-1}


by using formula of summation to simplify the equatoin(what a difficult job.....)
I get answer = (i - 1) * i * (i * i - 5 * i + 18) / 24 + 1;

---

Code In Java:

---

---

Code In C/C++:

---