← 返回题目列表

AtCoder · agc076_e

E. 平方范数最大化

中文机器翻译题面 查看原题

分数: 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,这是最大值。