AtCoder Beginner Contest 139 Task F Engines
题目大意
给定 $n$ 个二维向量，从中选出若干个，使得它们的和的模最大。
分析
这是一个经典问题，还有一种提法是：
给定 $n$ 个二维向量 $v_1, v_2, dots, v_n$，求一组系数 $a_1, a_2, dots, a_n$（$0 le a_i le 1$）使得 $sum_{i = 1}^{n} a_i v_i$ 的模最大。
容易证明：对于最优解，$a_i$ 要么是 1 要么是 0；于是归约到选择一个最优子集的问题。
可以证明，最优解满足下列两个性质：
- The set of vectors in an optimal solution using a minimal number of vectors must all lie in an open half-plane. 包含向量数目最少的最优解中，所有向量都在一个开的半平面中
如果加上「所选的向量都在一个开的半平面中」这个限制，我们立即可以推论出，若先把所有向量按极角排序，则所选的那些向量必定是其中连续的一段。换言之，
- 对于包含向量数目最少的最优解，其中的向量按极角排序后是连续的一段。The vectors in the optimal solution using a minimal number of vectors are contiguous when ordered according to angle circularly.