P7918 [Kubic] Lines

It is recommended to read the background of Problem C first.

In a 2D Cartesian coordinate system, there are $n$ lines. **No three lines intersect at one point, and no two lines coincide**. Obviously, these lines form at most $\dfrac{n(n-1)}{2}$ **intersection points**. You may choose a subset of these lines. A point is considered **covered** if and only if **at least one** of the chosen lines passes through it. Find the minimum number of lines to choose so that all **intersection points** are **covered**.

The first line contains an integer $n$. The next $n$ lines each contain three integers $a, b, c$, describing a line with equation $ax+by+c=0$. **Note: the input does not guarantee $\gcd(a,b)=1$.**

Output one line with one integer, representing the answer.

For $100\%$ of the testdata, $1 \le n \le 10^5$, $|a|, |b|, |c| \le 10^9$, and $a, b$ are not both $0$. ||Score|$n$|Special Property| |:-:|:-:|:-:|:-:| |$\operatorname{Subtask}1$|$10$|$\le 20$|None| |$\operatorname{Subtask}2$|$30$|$\le 100$|None| |$\operatorname{Subtask}3$|$10$|No special limit|$ab=0$| |$\operatorname{Subtask}4$|$50$|No special limit|None| ### Sample Explanation One way is to choose the two lines $x+2y+3=0$ and $4x+5y+6=0$. It can be proven that there is no better solution. Translated by ChatGPT 5