(hdu step 2.2.5) 삼각형 (n 개의 삼각형 이 평면 을 몇 부분 으로 나 눌 수 있 는 지 구하 기)

제목:
        
삼각형
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 653 Accepted Submission(s): 493
 
Problem Description
N 개의 삼각형 으로 평면 을 최대 몇 개의 구역 으로 나 눌 수 있 습 니까?
 
Input
입력 한 데이터 의 첫 줄 은 정수 T (1 < = T < = 10000) 로 테스트 데이터 의 수량 을 표시 합 니 다. 그 다음 에 T 조 테스트 데이터 입 니 다. 각 조 의 테스트 데 이 터 는 하나의 정수 N (1 < = N < = 10000) 만 포함 합 니 다.
 
Output
각 그룹의 테스트 데이터 에 대해 서 는 제목 에서 요구 하 는 결 과 를 출력 하 십시오.
 
Sample Input

2
1
2

 
Sample Output

2
8

 
Author
Ignatius.L
 
 
Recommend
Ignatius.L
 
제목 분석:
               수학 문제.전달 공식 은 ans [i] = ans [i - 1] + 6 * (i - 1) 이다. 유도 과정 은 다음 과 같다.
평면 자 체 는 1 부분 이다. 한 삼각형 은 평면 을 삼각형 내, 외 2 부분 으로 나 누 었 다. 즉, 1 부분 이 증가 했다. 두 삼각형 이 교차 하지 않 을 때 평면 을 3 부분 으로 나 누 었 다. 교차 할 때 교점 이 많 을 수록 나 누 는 부분 이 많다 (아래 그림 참조).위의 그림 에서 보 듯 이 새로 증가 한 부분 수 는 증가 한 교점 수 와 같 기 때문에 세 번 째 삼각형 을 그 릴 때 각 변 의 교점 을 최대한 많이 그 려 야 한다.각 삼각형 에 대해 서 는 1 개의 직선 이 삼각형 의 두 변 과 가장 많이 교차 하기 때문에 3 번 째 삼각형 의 각 변 은 최대 2 개의 삼각형 의 각 두 변 과 교차 하여 모두 3 이 생 길 수 있다.×（2×2) = 12 (개) 교점, 즉 12 부분 증가;따라서 3 개의 삼각형 은 평면 을 최대 1 + 1 + 6 + 12 = 20 (부분) 으로 나 눌 수 있다.위의 분석 을 통 해 n (n ≥ 2) 개의 삼각형 을 그 릴 때 각 변 은 앞 에 그 려 진 (n - 1) 개의 삼각형 의 각 두 변 과 가장 많이 교차 되 고 모두 교점 이 생 길 수 있다.×[（n-l）×2] = 6 (n - 1) (개), 6 (n - 1) 부분 을 새로 늘 릴 수 있 습 니 다. 1 개의 삼각형 이 있 을 때 2 부분 이 있 기 때문에 n 개의 삼각형 이 평면 을 가장 많이 나 누 는 부분 은: 2 + 6 입 니 다.×[1+2+…+（n-1）]=2+6×
n(n-1)
2
=2+3n（n-1），
n = 10 시: 2 + 3 로 나 눌 수 있 습 니 다.×10×(10 - 1) = 272 (부분).
답: 3 개의 삼각형 은 평면 을 최대 20 부분 으로 나 눌 수 있 고 10 개의 삼각형 은 평면 을 최대 272 부분 으로 나 눌 수 있다.
코드 는 다음 과 같 습 니 다:

/*
 * d.cpp
 *
 *  Created on: 2015 2 2 
 *      Author: Administrator
 */


#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 10005;

int a[maxn];

/**
 *  n            
 * a[i]: i             
 */
void init(){
	a[1] = 2;
	int i;
	for(i = 2 ; i < maxn ; ++i){
		a[i] = a[i-1] + 6*(i-1);
	}
}


int main(){
	init();

	int t;;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		printf("%d
",a[n]);
	}

	return 0;
}