Informatica Online Judge

  쿵! 쿵! [2167 / 0877]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 1   Total Tried : 1


The Champion of this Problem (C++) : gs17068 - 447ms / 1230byte
My Best Submission (C++) : N/A

[koistudy.net(33rd 신승원)]

Background

동규는 고급시계 게임을 아주 좋아한다. 고급정보과학 프로젝트로 시계를 만들 정도이니 말 다했다. 하지만 동규가 고급시계를 플레이하는 모습을 지켜 보면 정말로 좋아하는 것이 맞는 건지 의심이 들기도 한다.

"(쿵! 쿵! 딸깍딸깍딸깍) 아니 왜 거점을(쿵)! 안(쿵)! 들어와(쿵)! (딸깍딸깍)"

그렇게 마우스를 쿵쿵 내리치며 고급시계를 열심히 하던 어느 날, 드디어 책상이 깨지고 말았다! 그런데 깨진 책상을 보고 어이없어하던 동규는 신기한 사실을 발견했다. 책상에 간 금은 모두 자신이 마지막으로 내리친 점을 지나는 직선 또는 원이었던 것이다. 그 모양이 너무 예뻐서 동규는 그 모습을 사진으로 찍었다.

사진을 찍은 뒤 동규는 무심결에 깨진 책상을 손으로 톡 건드렸는데, 그 순간 책상이 금을 따라 조각나며 무너져 버렸다! 동규는 급히 책상 조각들을 주워 담았지만, 모든 조각을 주워 담은 게 맞는지 확실치 않았다. 그래서 동규는 금이 간 책상이 총 몇 조각으로 나뉘었는지를 알고 싶어한다.

다행히도 금 간 모습을 사진으로 찍어두었지만, 동규는 그 사진을 보고 일일이 조각 수를 세고 있기는 너무 싫었다. 동규를 위해 책상 조각 수를 세 주자!

Input

첫 번째 줄에는 원과 직선의 총 갯수 N (1≤N≤3000) 이 주어진다. 다음 N개의 줄에는 원 또는 직선 각각을 나타내는 수 3개가 주어지는데, 의미는 다음과 같다.

1 a b : 두 점 (0, 0)과 (a, b)를 지나는 직선을 나타낸다.

2 a b : 두 점 (0, 0)과 (a, b)를 잇는 선분을 지름으로 하는 원을 나타낸다.

(둘 모두에서 |a|,|b|≤106이고, a와 b 둘 중 하나는 0이 아님)

Output

첫 번째 줄에 원과 직선으로 나뉜 책상의 영역이 총 몇 개인지 출력한다.

책상은 충분히 커서 모든 원과 직선들의 교점이 책상 내부에 들어온다고 가정한다.

IO Example

입력
4
1 1 1
1 -1 1
2 0 2
2 2 0

출력
10

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]