A16769. Parabola Independence
编程题
普及+/提高
知识点
题目描述
给定 $n$ 个二次函数 $F=\{f_1, f_2, \ldots, f_n\}$，其中 $f_i(x) = a_i x^2 + b_i x + c_i$。
如果对于所有 $x \in \mathbb{R}$，都有 $f(x) \neq g(x)$，那么称函数 $f$ 和 $g$ 互为独立。
同样地，如果集合 $G=\{g_1, g_2, \ldots, g_k\}$ 中任意一对不同的函数 $g_i$ 和 $g_j$ 都互为独立（即对于 $1 \le i < j \le |G|$，都有 $g_i(x) \neq g_j(x)$ 对任意 $x \in \mathbb{R}$ 成立），那么称集合 $G$ 是有组织的。
对于每个 $i=1,2,\ldots,n$，请你求出包含 $f_i$ 的最大的有组织子集的大小。
如果对于所有 $x \in \mathbb{R}$，都有 $f(x) \neq g(x)$，那么称函数 $f$ 和 $g$ 互为独立。
同样地，如果集合 $G=\{g_1, g_2, \ldots, g_k\}$ 中任意一对不同的函数 $g_i$ 和 $g_j$ 都互为独立（即对于 $1 \le i < j \le |G|$，都有 $g_i(x) \neq g_j(x)$ 对任意 $x \in \mathbb{R}$ 成立），那么称集合 $G$ 是有组织的。
对于每个 $i=1,2,\ldots,n$，请你求出包含 $f_i$ 的最大的有组织子集的大小。
输入格式
每个测试点包含多组测试数据。第一行输入测试用例数 $t$（$1 \le t \le 10^4$）。接下来是每组测试数据。
每组数据的第一行输入一个整数 $n$（$1 \le n \le 3000$）。
接下来的 $n$ 行，每行输入三个整数 $a_i$、$b_i$、$c_i$，表示函数 $f_i$（$-10^6 \le a_i, b_i, c_i \le 10^6$，且 $a_i \neq 0$）。
保证每组数据中的函数两两不同。
保证所有测试用例的 $n^2$ 之和不超过 $3000^2$。
每组数据的第一行输入一个整数 $n$（$1 \le n \le 3000$）。
接下来的 $n$ 行，每行输入三个整数 $a_i$、$b_i$、$c_i$，表示函数 $f_i$（$-10^6 \le a_i, b_i, c_i \le 10^6$，且 $a_i \neq 0$）。
保证每组数据中的函数两两不同。
保证所有测试用例的 $n^2$ 之和不超过 $3000^2$。
输出格式
对于每组测试数据，输出 $n$ 个正整数 $s_1, s_2, \ldots, s_n$，其中 $s_i$ 表示包含 $f_i$ 的最大的有组织子集的大小。
输入输出样例
输入 #1
3 4 1 2 -1 -3 0 -3 -1 4 -5 1 2 -4 5 3 0 0 1 0 -5 -3 0 0 -1 0 10 1 0 -10 5 884 -667 497 680 -973 213 23 -548 -412 826 359 -333 773 212 218
输出 #1
3 2 3 3 3 3 2 2 3 3 3 3 1 2
说明/提示
在第一个测试用例中，函数如下：
- $f_1(x)=x^2+2x-1$；
- $f_2(x)=-3x^2-3$；
- $f_3(x)=-x^2+4x-5$；
- $f_4(x)=x^2+2x-4$。
它们的图像如下所示：
各个包含指定函数的最大有组织子集如下：
- $\{f_1, f_3, f_4\}$ 是包含 $f_1$ 的最大有组织子集；
- $\{f_1, f_2\}$ 是包含 $f_2$ 的最大有组织子集；
- $\{f_1, f_3, f_4\}$ 是包含 $f_3$ 的最大有组织子集；
- $\{f_1, f_3, f_4\}$ 是包含 $f_4$ 的最大有组织子集。
- $f_1(x)=x^2+2x-1$；
- $f_2(x)=-3x^2-3$；
- $f_3(x)=-x^2+4x-5$；
- $f_4(x)=x^2+2x-4$。
它们的图像如下所示：
各个包含指定函数的最大有组织子集如下：
- $\{f_1, f_3, f_4\}$ 是包含 $f_1$ 的最大有组织子集；
- $\{f_1, f_2\}$ 是包含 $f_2$ 的最大有组织子集；
- $\{f_1, f_3, f_4\}$ 是包含 $f_3$ 的最大有组织子集；
- $\{f_1, f_3, f_4\}$ 是包含 $f_4$ 的最大有组织子集。