简要题意
给出 \(n\) 个向量,求其子集的和的最大模长。
\(1 \leq n \leq 100\)
思路
先说结论:选出的几个向量,一定是极角排序后的某一段(环形)区间。
这个不难感性理解,比如下图:
于是我们对向量极角排序后破环成链,然后暴力枚举区间即可。
时间复杂度 \(O(n^2)\)。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
struct Vector{
double x,y;
double polar() const {
return atan2(y,x);
}
double len() const {
return sqrt(x*x+y*y);
}
Vector operator+(const Vector v) const {
return {x+v.x,y+v.y};
}
} vct[205];
double ans;
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>vct[i].x>>vct[i].y;
}
sort(vct+1,vct+n+1, [&](Vector x,Vector y){
return x.polar()<y.polar();
});
for(int i=1;i<=n;i++) vct[i+n]=vct[i];
for(int i=1;i<=n;i++){
Vector v={0,0};
for(int j=i;j<(i+n);j++){
v=v+vct[j];
ans=max(ans, v.len());
}
}
cout<<fixed<<setprecision(48)<<ans;
return 0;
}