아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

쿵! 쿵!

시간 제한2초메모리 제한512 MB

요약
모두 원점을 지나는 직선과 원들이 평면을 몇 개의 영역으로 나누는지 구한다. 같은 도형은 하나로 센다.
난이도

어려움10점 중 8점

유형
기하, 조합론, 수학, 구현
정답자
아직 제출이 없습니다

문제

동규는 게임을 하다가 마우스를 쿵쿵 내리치는 버릇이 있다. 그렇게 마우스를 내리치며 게임을 하던 어느 날, 책상이 깨지고 말았다. 깨진 책상을 보니 금이 간 자리가 모두 마지막으로 내리친 점을 지나고 있었다. 어떤 금은 직선이었고, 어떤 금은 그 점을 지나는 원이었다. 동규는 그 모습을 사진으로 찍어 두었다.

사진을 찍은 뒤 책상을 톡 건드리자, 책상은 금을 따라 조각나며 무너졌다. 동규는 조각을 모두 주웠는지 확인하고 싶어 한다. 사진에 남은 금을 보고 책상이 몇 조각으로 나뉘었는지 세어 주자.

마지막으로 내리친 점을 원점 (0,0)(0, 0)으로 두면, 금은 모두 원점을 지나는 직선이거나 원점을 지나는 원이다. 이 직선과 원이 평면을 몇 개의 영역으로 나누는지 구한다.

입력

첫째 줄에 원과 직선의 총 개수 NN (1≤N≤3 0001 \le N \le 3\,000)이 주어진다. 다음 NN개의 줄에는 원 또는 직선을 나타내는 정수 세 개가 주어지며, 의미는 다음과 같다.

  • 1 a b : 두 점 (0,0)(0, 0)과 (a,b)(a, b)를 지나는 직선
  • 2 a b : 두 점 (0,0)(0, 0)과 (a,b)(a, b)를 잇는 선분을 지름으로 하는 원

두 경우 모두 ∣a∣,∣b∣≤106|a|, |b| \le 10^{6}이고, aa와 bb가 동시에 00인 경우는 없다. 같은 직선이나 같은 원이 여러 번 주어질 수 있으며, 겹치는 도형은 하나로 센다.

출력

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

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

예제3

  1. 예제 1

    입력
    4
    1 1 1
    1 -1 1
    2 0 2
    2 2 0
    
    예상 출력
    10
    
  2. 예제 2

    입력
    1
    1 3 -4
    
    예상 출력
    2
    
  3. 예제 3

    입력
    1
    2 -1000000 1000000
    
    예상 출력
    2