A6124. 「USACO 2022.1 Platinum」Multiple Choice Test
编程题
省选/NOI-
知识点
题目描述
奶牛们正在参加一个选择题测试。在通常的测试中，对每个问题你的选项会被单独评分然后累加，而在此测试中，你的选项在累加之后再评分。
具体地说，你被给定二维平面上的 $N$（$2≤N≤10^5$）组整数向量，其中每个向量用一个有序对 $(x,y)$ 表示。从每组中选择一个向量，使向量的总和尽可能远离原点。
输入保证向量的总数不超过 $2⋅10^5$。每组至少包含 $2$ 个向量，并且一组内所有向量各不相同。输入同时保证每个 $x$ 和 $y$ 坐标的绝对值不超过 $\frac{10^9}N$。
具体地说，你被给定二维平面上的 $N$（$2≤N≤10^5$）组整数向量，其中每个向量用一个有序对 $(x,y)$ 表示。从每组中选择一个向量，使向量的总和尽可能远离原点。
输入保证向量的总数不超过 $2⋅10^5$。每组至少包含 $2$ 个向量，并且一组内所有向量各不相同。输入同时保证每个 $x$ 和 $y$ 坐标的绝对值不超过 $\frac{10^9}N$。
输入格式
输入的第一行包含 $N$，为向量的组数。
每一组的第一行包含 $G$，为组中的向量数。以下 $G$ 行包含组中的向量。相邻组之间用空行分隔。
每一组的第一行包含 $G$，为组中的向量数。以下 $G$ 行包含组中的向量。相邻组之间用空行分隔。
输出格式
输出最大可能的欧几里得距离的平方。
输入输出样例
输入 #1
3 2 -2 0 1 0 2 0 -2 0 1 3 -5 -5 5 1 10 10
输出 #1
242
说明/提示
- 测试点 1-5 中，向量的总数不超过 $10^3$。
- 测试点 6-9 中，每一组恰好包含 $2$ 个向量。
- 测试点 10-17 没有额外限制。
- 测试点 6-9 中，每一组恰好包含 $2$ 个向量。
- 测试点 10-17 没有额外限制。