Multiple Choice Test

题目描述

奶牛们正在参加一场选择题考试。但与标准考试不同的是：标准考试会对你在每道题选择的选项分别计分再求和；而这场考试会先把你选择的选项求和，然后再计分。 具体而言，给定 $N$（$2\le N\le 10^5$）组位于二维平面上的整数向量，每个向量用有序对 $(x,y)$ 表示。你需要从每一组中选择一个向量，使得所选向量之和距离原点尽可能远。 保证向量总数不超过 $2\cdot 10^5$。 每组大小至少为 $2$，且同一组内所有向量互不相同。 还保证每个 $x$ 和 $y$ 坐标的绝对值最多为 $\frac{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$。 SCORING: 在测试点 1-5 中，向量总数最多为 $10^3$。 在测试点 6-9 中，每组大小恰好为二。 测试点 10-17 没有额外限制。 题目来源：Benjamin Qi

标签: USACO|2022|Platinum

来源

USACO|2022|Platinum