재하의 장난감
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- TOYOFJAEHA
- 10000ms
- 131072kb
- 97
- 18 (18%)
-
- 출처
- 분류
문제
얼마 전에 태어난 깜짝 스타 재하는 순식간에 무럭무럭 자랐다. 누구를 닮았는지 호기심이 유달리 강해 주위
사물들에 손을 뻗어서 만지작거리곤 하는데, 재하의 아버지와 어머니는 이러한 재하를 위해서 장난감을 한 개
사다 주었다. 이 장난감은 선분과 선분이 환형으로 연결된 모양이라, 아이가 입에 넣는 것이 쉽지 않도록 되어
있다.
재하는 장난기가 발동하여 다음과 같은 다양한 모양으로 장난감을 이리저리 흐트러트리기 시작했다.
엄밀하게 말하자면, 이 장난감은 (x_1, y_1), (x_2, y_2), ..., (x_n, y_n), (x_1, y_1) 의 인접한 점들을 선분으로 이은 교차점이나 교차선이 있을 수 있는 다각형으로 정의된다.
이 장난감이 만들어낸 넓이가 0이 넘는 영역의 수를 구하라. 단, 이 장난감 가장 바깥에 원래부터 존재하고 있었던 무한대 넓이의 영역은 세지 않는 것으로 한다.
입력
입력은 T 개의 테스트 케이스로 구성된다. 입력의 첫 행에는 T 가 주어진다.
각 테스트 케이스의 첫 행에는 장난감을 이루는 꼭지점의 수 N (3 <= N <= 100) 이 주어진다. 그 후 N 줄에 각 꼭지점의 좌표 x_i, y_i (0 <= x_i, y_i <= 100) 가 주어진다. 각 테스트 케이스 안에서, 같은 좌표의 꼭지점은 입력으로 들어오지 않는다.
출력
각 테스트 케이스마다 한 행에 하나씩 문제에서 설명한 영역의 수를 출력한다.
예제 입력
2 4 0 1 1 0 1 1 0 0 6 0 0 1 0 1 1 2 1 2 0 3 0
예제 출력
2 1
노트