/ 
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 1400 点
問題文
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)
スコアとしてありうる最大値を求めてください．
1 つの入力につき，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
- T ケースにわたる N の総和は 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
1 つ目のケースでは，s=\{\} とするとスコアが 0 になり，これが最大です．
2 つ目のケースでは，s=\{1,2,3,4\} とするとスコアが 4 になり，これが最大です．
Score : 1400 points
Problem Statement
You are given N pairs of integers (A_1,B_1),(A_2,B_2),\cdots,(A_N,B_N).
For a subset s of \{1,2,\cdots,N\}, we define its score as follows:
- (\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)
Find the maximum possible value of the score.
Solve T cases for one input.
Constraints
- 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
- The sum of N over the T cases is at most 250000.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_T
Each test case is given in the following format:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Output T lines. The i-th line should contain the answer for the i-th case.
Sample Input 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
Sample Output 1
0 4 296 178262497119089558
In the first case, if s=\{\}, the score is 0, which is the maximum.
In the second case, if s=\{1,2,3,4\}, the score is 4, which is the maximum.