分数: 1400 点
问题陈述
你被给予 N 整数对 (A_1,B_1),(A_2,B_2),\cdots,(A_N,B_N).
对于子集 s of \{1,2,\cdots,N\},我们定义它 分数 如下:
- (\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 一个输入的情况。
约束
- 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 超过 T 例最多 250000.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
4 4 1 0 0 1 -1 0 0 -1 4 1 0 1 0 1 0 1 0 6 1 -9 -7 -2 0 -10 10 1 2 -8 1 -8 10 19271058 -140039457 -3441379 -134156148 227767903 -70474702 -837477 -74699717 153584327 80404336 115741008 -22141349 -190028077 -21940357 76149725 17176032 159846847 -296045185 -53332199 142922717
示例输出 1
0 4 296 178262497119089558
在第一种情况下,如果 s=\{\},得分为 0,这是最大值。
在第二种情况下,如果 s=\{1,2,3,4\},得分为 4,这是最大值。