P6981: 多项选择测试
传统题
1.000s
时间限制
256MB
内存限制
3 提交
1 解决
【题目描述】
【题目描述】
奶牛们正在参加一个选择题测试。在通常的测试中，对每个问题你的选项会被单独评分然后累加，而在此测试中，你的选项在累加之后再评分。
具体地说，你被给定二维平面上的 N
（2≤N≤10
^5
）组整数向量，其中每个向量用一个有序对 (x,y)
表示。从每组中选择一个向量，使向量的总和尽可能远离原点。
输入保证向量的总数不超过 2
*10
^5
。每组至少包含 2
个向量，并且一组内所有向量各不相同。输入同时保证每个 x 和 y 坐标的绝对值不超过 10^9
/N
。
【
输入格式】
（从终端 /
标准输入读入）：
输入的第一行包含 N
，为向量的组数。
每一组的第一行包含 G
，为组中的向量数。以下 G
行包含组中的向量。相邻组之间用空行分隔。
【
输出格式】
（输出至终端 /
标准输出）：
输出最大可能的欧几里得距离的平方。
【
输入样例】
：
3
2
-2 0
1 0
2
0 -2
0 1
3
-5 -5
5 1
10 10
【
输出样例】
：
242
【样例说明】
最优方案是从第一组选择(1,0)
，从第二组中选择(0,1)
，从第三组选择 (10,10)
。这些向量之和等于(11,11)
，与原点的距离平方等于 11
^2+11
^2=242
。
【
测试点性质】
：
测试点 1-5
中，向量的总数不超过 10^3
。
测试点 6-9
中，每一组恰好包含 2 个向量。
测试点 10-17
没有额外限制。