17368번 - 교점 세기

자연상수 $e = 2.7182818284590452353602874\cdots$는 자연로그의 밑(base of the natural logarithm)으로, 아래와 같이 표현할 수 있음이 알려져 있다.

$$e = \lim_{t \rightarrow \infty} \left(1+\frac{1}{t}\right)^t = \sum_{k=0}^{\infty} \frac{1}{k!}$$

정의역이 집합 $X$이고 공역이 집합 $Y$인 함수 $f : X \rightarrow Y$의 그래프는 입력과 출력의 순서쌍으로 이루어진 집합, 즉

$$\left\{ \left(x, f(x)\right) : x \in X\right\}$$

로 정의된다. $X$와 $Y$가 모두 실수로 이루어진 집합이라면, 함수의 그래프에 속한 점들을 2차원 좌표평면 위에 나타낼 수 있다.

이 문제에서 다룰 함수는 "y=e?(ax)"과 같은 꼴이다. 여기서 ?는 곱셈 연산자 *, 나눗셈 연산자 /, 거듭제곱 연산자 ^ 중 하나이고, a는 정수이다. 단, 연산자가 /인 경우 a는 0이 아님이 보장된다.

함수의 정의역은 ?가 * 또는 ^인 경우 전체 실수 집합($\mathbb{R}$)이고, /인 경우 0을 제외한 모든 실수($\mathbb{R} \setminus \{0\}$)이다. 함수의 공역은 실수 집합($\mathbb{R}$)이다. 모든 경우에 대해 함수의 정의역과 공역은 실수로 이루어진 집합이므로, 이 문제에서 다룰 모든 함수는 좌표평면 위에 그래프를 그릴 수 있다.

아래 그림은 연산자 ?와 정수 a의 값에 따라 달라지는 함수의 그래프 몇 가지를 나타낸다.

여러분은 위 그림과 같이 좌표평면 위에 주어진 함수들의 그래프를 모두 그렸을 때, 서로 다른 교점의 개수를 세는 프로그램을 작성해야 한다. 여기서 어떤 점이 교점이라는 것은 이 점이 주어진 함수 중 2개 이상의 그래프에 동시에 포함되어 있다는 것이다. 즉, 어떤 점이 3개 이상의 그래프에 동시에 포함되어 있더라도 한 번만 세어야 한다. 위 그림에서는 교점이 2개 있다.

첫 번째 줄에 함수의 개수 n(1 ≤ n ≤ 300,000)이 주어진다. 다음 n개의 줄에는 함수 n개의 정보가 한 줄에 하나씩 주어지며, 각 줄에는 연산자 ? (*, /, ^ 중 하나)와 정수 a(-10⁶ ≤ a ≤ 10⁶)가 공백 하나를 사이로 두고 주어진다.

주어지는 모든 함수는 서로 다르며, 연산자 ?가 /라면 a는 0이 아니다.

첫 번째 줄에 좌표평면 위에 주어진 모든 함수의 그래프를 그렸을 때 나타나는 교점의 수를 출력한다.