标签：POI2018 return int long vect operator 向量
题意
给出 \(n\) 个平面向量，要求选择一些向量使它们和的模长最大，输出最大模长。
题解
假设已知答案向量方向，观察题目可以发现，只有在答案向量方向投影为正的向量才会对结果产生贡献。由此考虑枚举所有方向。
对所有向量的极角排序，排序后可以确定选取的向量一定是连续的一段。考虑使用双指针求解。所有的向量形成一个环，因此处理时需要复制一份求解，然后双指针枚举左右端点即可得出结果。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
const int maxn=2e5+10;
const double PI=acos(-1);
struct vect{
int x,y;
double theta;
vect operator+(vect a){
return {x+a.x,y+a.y};
}
vect operator-(vect a){
return {x-a.x,y-a.y};
}
bool operator<(const vect &a)const{
return theta<a.theta;
}
};
vect vec[maxn<<1];
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&vec[i].x,&vec[i].y);
vec[i].theta=atan2(vec[i].y,vec[i].x);//求极角
vec[i+n].x=vec[i].x;
vec[i+n].y=vec[i].y;
vec[i+n].theta=vec[i].theta+2*PI;
}
sort(vec+1,vec+2*n+1);
int l=1,r=1;
vect ans={0,0,0},res={0,0,0};
for(int l=1;l<=n;l++){
while(r<=n+l-1&&vec[r].theta-vec[l].theta<PI){
res=res+vec[r];
if(ans.x*ans.x+ans.y*ans.y<res.x*res.x+res.y*res.y){
ans=res;
}
r++;
}
res=res-vec[l];
if(ans.x*ans.x+ans.y*ans.y<res.x*res.x+res.y*res.y){
ans=res;
}
}
printf("%lld",ans.x*ans.x+ans.y*ans.y);
return 0;
}
标签：POI2018,
return,
int,
long,
vect,
operator,
向量
From： https://www.cnblogs.com/qianbj/p/17723839.html