题解：P5955 [POI2018] Pionek

ZhongYuLin · 2024-07-16 07:43:19 · 题解

显然只有处于一个半平面内的向量集合才有可能成为答案。去考虑枚举半平面。考虑用一个与分割线正交的方向向量来刻画这个半平面

我们将所有的向量按辐角主值排序。设答案向量为 \mathbf{x}，其初始指向纵轴正方向，然后将其沿原点绕一圈。具体地，每次逆时针旋转 \varepsilon \operatorname{rad}，直到回到起始点。 不难发现，答案在排序后总是一段区间，于是将原序列复制一份后使用双指针，注意重复的问题。

对于区间右端点，如果当前向量与 \mathbf{x} 的夹角小于等于 \frac{1}{2}\pi，加入。

对于区间左端点，如果当前向量与 \mathbf{x} 的夹角大于 \frac{1}{2}\pi，删除。

然而，我们不必构造 \mathbf{x} 然后借助内积，我们可以直接使用辐角主值。具体地：

注意一下 \varepsilon 的数量级和精度误差就可以了。

复杂度 O(n\log n+\frac{1}{\varepsilon})。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=4e5+3;
const double PI=acos(-1),eps=1e-6;
struct Vec{
    int x,y;
    double tan;
}v[N];
int n;
double calc(double t1,double t2){return min(abs(t1-t2),2*PI-abs(t1-t2));}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>v[i].x>>v[i].y;
        if(!v[i].x&&!v[i].y){--i,--n;continue;}
        v[i].tan=atan2(v[i].y,v[i].x);
        if(v[i].tan<0)v[i].tan+=2*PI;
    }
    sort(v+1,v+1+n,[&](Vec x,Vec y){return x.tan<y.tan;});
    for(int i=1;i<=n;++i)v[i+n]=v[i];
    int l=1,r=1;double it=PI/2;ll x=0,y=0,ans=0;
    for(;it<=PI*5/2;it+=eps){
        double at=it;
        if(at>2*PI)at-=2*PI;
        while(r<=l+n-1&&calc(v[r].tan,at)*2<=PI)
            x+=v[r].x,y+=v[r].y,ans=max(ans,x*x+y*y),++r;
        while(l<r&&calc(v[l].tan,at)*2>PI)
            x-=v[l].x,y-=v[l].y,ans=max(ans,x*x+y*y),++l;
    }printf("%lld\n",ans);
    return 0;
}