10213.How many pieces of land

>> বুধবার, ১৮ নভেম্বর, ২০০৯

You are given an elliptical shaped land and you are asked to choose n arbitrary points on its boundary. Then you connect all these points with one another with straight lines (that’s n*(n-1)/2 connections for n points). What is the maximum number of pieces of land you will get by choosing the points on the boundary carefully?

Fig: When the value of n is 6.

The first line of the input file contains one integer S (0 < S < 3500), which indicates how many sets of input are there. The next S lines contain S sets of input. Each input contains one integer N (0<=N<2^31).

For each set of input you should output in a single line the maximum number pieces of land possible to get for the value of N.

Sample Input:
4 Sample Output:
Description: presented by rizoan toufiq
F(N) = ( N * (N-1) * (N*N-5*N+18) / 24 ) + 1
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;

একটি মন্তব্য পোস্ট করুন

  © Rizoan Toufiq , Copy Right @ 2009

Back to TOP