문제1769--볼록 다각형의 삼각분할

1769: 볼록 다각형의 삼각분할

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 277  통과: 220
[제출] [채점기록] [묻고답하기]

문제 설명

3D 엔진 프로그래머의 꿈을 갖고 있는 신입생 Noname은 공간상의 다각형을 Polygon이라고 부르는 삼각형으로 분할하여 표현할 수 있다는 것을 선배로부터 듣게 되었다.

이미지 출처 :  http://www.codersources.net , OpenGL tutorial 7 
 
모든 과정은 첫 걸음부터 시작해야 하는 법. 복잡한 공간상의 기하학적 데이터를 다루기에 앞서 Noname은 일단 평면상의 볼록 다각형을 삼각형으로 분할하는 작업을 수행해 보기로 했다. 그런데 신입생 Noname은 수능이 끝난 다음 중고등학교에서 배웠던 내용을 모두 잊어버리고 말아 선배인 당신에게 볼록 N-다각형이 최대 몇개의 삼각형으로 분할될 수 있는지 문의하기로 했다.
 
취업준비에 시간이 촉박한 선배인 당신은 볼록 N-다각형이 최대 몇 개의 삼각형으로 분할되는지 매번 가르쳐주는 대신, 이에 대한 정답을 가르쳐 주는 프로그램을 작성해 주기로 한다. ( 단, 분할된 삼각형은 서로 겹칠 수 없으며, 또한 각 삼각형은 볼록 N-다각형의 꼭지점을 연결하는 선분으로만 분할될 수 있다.)

입력 설명

입력은 여러개의 테스트 케이스로 이뤄지면 입력의 첫 줄에는 테스트 케이스의 개수 $T$ 가 주어진다. $( 1 \leq T \leq 100)$

각 테스트 케이스는 한줄에 정수 하나로 이뤄져 있으며, 이는 볼록 $N$-다각형의 $N$을 뜻한다. $( 0 \leq N \leq 1, 000 )$

출력 설명

볼록 $N$-다각형이 최대 몇 개의 서로 겹치지 않는 삼각형으로 분할될 수 있는지 출력하도록 한다. 단, 삼각형이 단 1개 이상으로 구성될 수 없을 때, 즉, 다각형이 구성되지 않을 때는 -1을 출력하도록 한다.

입력 예시 Copy

3
3
5
2

출력 예시 Copy

1
3
-1