题目描述

给你 $n$ 个平面向量，选出它们中的一部分，使得它们的和的长度最大。求这个最大长度的平方。

输入

第一行包含一个正整数n(n<=200000)，表示指令条数。

接下来n行，每行两个整数x,y(|x|,|y|<=10000)，表示你可以从(a,b)移动到(a+x,b+y)。

输出

输出一行一个整数，即最大距离的平方。

样例输入

5

2 -2

-2 -2

0 2

3 1

-3 1

样例输出

26

---

题解

双指针法

一个结论：向量和的长度等于所有向量在其方向上投影的长度和。

因此想要向量和的长度最大，即要选择所有在其方向上投影长度为正的向量。

由于与一个向量夹角在 $(-\frac\pi2,\frac\pi2)$ 范围内的向量在其方向上投影为正，因此所求的就是对于任何一个长度为 $\pi$ 的区间包含的所有向量的和长度的最大值。

对于区间左端点为某个给定向量的，可以通过双指针法来维护向量和。

对于区间左端点不为某个给定向量的，可以在双指针每一步（尾部加向量、头部删向量）后都统计一遍答案。容易发现这样一定是正确的。

时间复杂度为排序的 $O(n\log n)$ 

#include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long ll;const double pi = acos(-1);struct data{	ll x , y;	double ang;	bool operator<(const data &a)const {return ang < a.ang;}}a[400010];int main(){	int n , i , p;	ll sx = 0 , sy = 0 , ans = 0;	scanf("%d" , &n);	for(i = 1 ; i <= n ; i ++ ) scanf("%lld%lld" , &a[i].x , &a[i].y) , a[i].ang = atan2(a[i].y , a[i].x);	sort(a + 1 , a + n + 1);	for(p = i = 1 ; i <= n ; i ++ )	{		while(p < i + n && a[p].ang - a[i].ang < pi) sx += a[p].x , sy += a[p ++ ].y , ans = max(ans , sx * sx + sy * sy);		sx -= a[i].x , sy -= a[i].y , ans = max(ans , sx * sx + sy * sy);;		a[i + n].x = a[i].x , a[i + n].y = a[i].y , a[i + n].ang = a[i].ang + 2 * pi;	}	printf("%lld\n" , ans);	return 0;}