题解：P10671 BZOJ1278 向量 vector

· · 题解

Solution

典题，似乎做过。

结论：必定能找到一条直线，使得选取这条直线某一侧的所有点达到答案最大。（严格意义上同一侧，这条线上的点不选）

假设最终的向量是 \vec v，我们取垂直于它的直线 l。显然不可能有向量严格与 l 重合，否则随便调整会使长度增加；如果 l 和 \vec v 同侧有一个向量没有被选中，选上他会让 \vec v 增加，矛盾；如果 l 和 \vec v 异侧有一个向量被选中了，将他取反就相当于撤销，这时候发现也是不优的。

如何找到 l？

一种想法是直接随机化，我不是很懂其正确性。

确定性做法是考虑双指针，将向量极角排序后维护两个指针 l 和 r，使得排序后的第 l 个向量和第 r 个向量夹角严格小于 \pi。

这样一定会覆盖所有满足要求的集合。取最大值即可。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=100000+10;
int n;
struct VEC {double x,y;}v[MAXN<<1],s;
double ans;
int getsq(VEC v) {
    if(v.x>=0&&v.y>=0) return 1;
    if(v.x<0&&v.y>=0) return 2;
    if(v.x<0&&v.y<0) return 3;
    return 4;   
}
bool operator <(VEC a,VEC b) {
    if(getsq(a)!=getsq(b)) return getsq(a)<getsq(b);
    return a.x*b.y-a.y*b.x>0;
}
VEC operator +(VEC A,VEC B) {return {A.x+B.x,A.y+B.y};}
VEC operator -(VEC A,VEC B) {return {A.x-B.x,A.y-B.y};}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    ffor(i,1,n) cin>>v[i].x>>v[i].y;
    VEC vc={0,0};
    ffor(i,1,n) vc=vc+v[i];
    sort(v+1,v+n+1);
    ffor(i,1,n) v[i+n]=v[i];
    int l=1,r=1; s=v[1],ans=max(ans,s.x*s.x+s.y*s.y);
    while(v[l].x*v[r+1].y-v[l].y*v[r+1].x>0) {
        r++,s=s+v[r],ans=max(ans,s.x*s.x+s.y*s.y);
    }   
    ffor(i,2,n) {
        l++,s=s-v[l-1];
        if(r<l) s=v[l],r=l;
        ans=max(ans,s.x*s.x+s.y*s.y);
        while(v[l].x*v[r+1].y-v[l].y*v[r+1].x>0) {
            r++,s=s+v[r],ans=max(ans,s.x*s.x+s.y*s.y);
        }
    }
    cout<<fixed<<setprecision(3)<<ans;
    return 0;
}