欧拉定理 V-E+F=C+1
Problem G
How Many Pieces of Land?
Input: Standard Input
Output: Standard Output
Time Limit: 3 seconds
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.
Input
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)<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPi48L3A+CjxwPiA8L3A+CjxwPjxzdHJvbmc+T3V0cHV0PC9zdHJvbmc+PC9wPgo8cD5Gb3IgZWFjaCBzZXQgb2YgaW5wdXQgeW91IHNob3VsZCBvdXRwdXQgaW4gYSBzaW5nbGUgbGluZSB0aGUgbWF4aW11bSBudW1iZXIgcGllY2VzIG9mIGxhbmQgcG9zc2libGUgdG8gZ2V0IGZvciB0aGUgdmFsdWUgb2YgPHN0cm9uZz5OPC9zdHJvbmc+LjwvcD4KPHA+PHN0cm9uZz4gPC9zdHJvbmc+PC9wPgo8cD48c3Ryb25nPlNhbXBsZSBJbnB1dDo8L3N0cm9uZz48L3A+CjQ8YnI+CjE8YnI+CjI8YnI+CjM8YnI+CjQ8YnI+Cjxicj4KPHA+IDwvcD4KPHA+PHN0cm9uZz5TYW1wbGUgT3V0cHV0Ojwvc3Ryb25nPjwvcD4KMTxicj4KMjxicj4KNDxicj4KODxicj4KCjxociBzaXplPQ=="2" width="100%" align="center">
Shahriar Manzoor
/**
* Created by ckboss on 15-2-1.
*/
import java.math.BigInteger;
import java.util.*;
public class Main {
BigInteger pfh(BigInteger n){
return n.multiply((n.add(BigInteger.ONE))).multiply((n.multiply(BigInteger.valueOf(2))).add(BigInteger.ONE)).divide(BigInteger.valueOf(6));
}
BigInteger getV(BigInteger n){
BigInteger A = n.subtract(BigInteger.valueOf(2));
BigInteger B = n.subtract(BigInteger.valueOf(3));
BigInteger temp = A.multiply(B).divide(BigInteger.valueOf(2)).multiply(A).subtract(pfh(B));
temp = temp.multiply(n).divide(BigInteger.valueOf(4));
return temp.add(n);
}
BigInteger getE(BigInteger n){
BigInteger A = n.subtract(BigInteger.valueOf(2));
BigInteger B = n.subtract(BigInteger.valueOf(3));
BigInteger temp = A.multiply(B).divide(BigInteger.valueOf(2)).multiply(A).subtract(pfh(B)).add(n).subtract(BigInteger.ONE);
temp = temp.multiply(n).divide(BigInteger.valueOf(2));
return temp.add(n);
}
Main(){
Scanner in = new Scanner(System.in);
int T_T = in.nextInt();
while(T_T-->0) {
BigInteger n = in.nextBigInteger();
BigInteger V = getV(n);
BigInteger E = getE(n);
BigInteger F = BigInteger.ONE.subtract(V).add(E);
System.out.println(F);
}
}
public static void main(String[] args){
new Main();
}
}