AT_agc076_e [AGC076E] Squared Norm Maximization
题目描述
给定 $N$ 对整数 $(A_1, B_1), (A_2, B_2), \cdots, (A_N, B_N)$。
对于 $\{1,2,\cdots,N\}$ 的任意子集 $s$，我们定义它的**得分**为：
- $ (\sum_{i \in s} A_i)^2 + (\sum_{i \in s} B_i)^2 - 3 \sum_{i \in s} (A_i^2 + B_i^2) $
请你求出得分的最大可能值。
本题包含 $T$ 组测试数据。
输入格式
输入从标准输入读入，格式如下：
> $T$
> $case_1$
> $case_2$
> $\vdots$
> $case_T$
其中每组测试数据格式如下：
> $N$
> $A_1$ $B_1$
> $A_2$ $B_2$
> $\vdots$
> $A_N$ $B_N$
输出格式
输出共 $T$ 行，第 $i$ 行输出第 $i$ 组数据的答案。
说明/提示
### 样例解释 1
对于第一个测试点，当 $s=\{\}$ 时，得分为 $0$，为最大值。
对于第二个测试点，$s=\{1,2,3,4\}$ 时得分为 $4$，为最大值。
### 数据范围
- $1 \leq T \leq 250000$
- $1 \leq N \leq 250000$
- $\sum_{1 \leq i \leq N} |A_i| \leq 10^9$
- $\sum_{1 \leq i \leq N} |B_i| \leq 10^9$
- 所有测试点中 $N$ 的总和不超过 $250000$。
- 所有输入值均为整数。
由 ChatGPT 5 翻译