레이팅 미적용소들이 객관식 시험을 치르고 있다. 그런데 각 문항마다 선택한 답을 개별적으로 채점한 뒤 합산하는 일반적인 시험과 달리, 이 시험에서는 선택한 답들을 먼저 합산한 뒤에 채점한다.
구체적으로, 2차원 평면 위의 정수 벡터들로 이루어진 \(N\) (\(2\le N\le 10^5\))개의 그룹이 주어지며, 각 벡터는 순서쌍 \((x,y)\)로 표현된다. 각 그룹에서 벡터를 하나씩 선택하여 벡터들의 합이 원점에서 최대한 멀어지도록 하라.
전체 벡터의 수는 최대 \(2\cdot 10^5\)임이 보장된다. 각 그룹의 크기는 2 이상이며, 한 그룹 안의 벡터들은 모두 서로 다르다. 또한 모든 \(x\)와 \(y\) 좌표의 절댓값이 \(\frac{10^9}{N}\) 이하임이 보장된다.
출제자: Benjamin Qi
배점
- 테스트 케이스 1-5에서는 전체 벡터의 수가 \(10^3\) 이하이다.
- 테스트 케이스 6-9에서는 모든 그룹의 크기가 정확히 2이다.
- 테스트 케이스 10-17에는 추가 제약이 없다.
출제자: Benjamin Qi
첫째 줄에 그룹의 수 \(N\)이 주어진다.
각 그룹은 그룹에 속한 벡터의 수 \(G\)로 시작하며, 이어서 \(G\)개의 줄에 그 그룹의 벡터들이 주어진다. 연속한 그룹 사이에는 빈 줄이 있다.
가능한 유클리드 거리 제곱의 최댓값을 출력한다.
3
2
-2 0
1 0
2
0 -2
0 1
3
-5 -5
5 1
10 10242It is optimal to select \((1,0)\) from the first group, \((0,1)\) from the second
group, and \((10,10)\) from the third group. The sum of these vectors is
\((11,11)\), which is squared distance \(11^2+11^2=242\) from the origin.
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > January > Platinum