만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

인피니스탄의 땅

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

요약
직선 벽 n개와 이차 곡선 모양의 강이 평면을 나누는 영역의 개수를 구합니다.
난이도

어려움10점 중 8점

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

문제

인피니스탄 나라는 무한한 평면으로 표현할 수 있다. 이 나라에는 직선 벽 nn개와 2차 곡선 형태의 강이 있다. 강은 타원, 포물선, 쌍곡선 중 하나다. 벽과 강은 나라를 넓이가 0이 아닌 여러 개의 땅으로 나눈다. 주어진 모든 방정식을 바탕으로 그 땅의 개수를 구하라.

입력

첫째 줄에 직선 벽의 개수 nn이 주어진다 (1≤n≤201 \le n \le 20).

둘째 줄에 강을 나타내는 2차 곡선 q0⋅x2+q1⋅xy+q2⋅y2+q3⋅x+q4⋅y+q5=0q_0 \cdot x^2 + q_1 \cdot xy + q_2 \cdot y^2 + q_3 \cdot x + q_4 \cdot y + q_5 = 0의 계수 q0q_0, q1q_1, q2q_2, q3q_3, q4q_4, q5q_5가 정수로 주어진다.

이어지는 nn개의 줄에는 직선 ai⋅x+bi⋅y+ci=0a_i \cdot x + b_i \cdot y + c_i = 0의 계수 aia_i, bib_i, cic_i가 정수로 한 줄에 하나씩 주어진다.

모든 qiq_i, aia_i, bib_i, cic_i의 절댓값은 100 이하다. 직선끼리는 겹칠 수 있다. 2차 곡선은 퇴화하지 않았으며, 모든 ii에 대해 aia_i와 bib_i 중 적어도 하나는 0이 아니다.

출력

땅의 개수를 정수 하나로 출력한다.

예제3

  1. 예제 1

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

    입력
    2
    1 0 0 0 -1 0
    2 -1 -1
    6 9 1
    
    예상 출력
    7
    
  3. 예제 3

    입력
    2
    1 0 -1 0 0 -1
    3 0 6
    -5 0 -10
    
    예상 출력
    6