自动搬运

查看原文

来自洛谷，原作者为

	ZhongYuLin 天若有情天亦老，人间正道是沧桑

搬运于2025-08-24 22:15:57，当前版本为作者最后更新于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}$ 然后借助内积，我们可以直接使用辐角主值。具体地：

$$\langle\mathbf{x},\mathbf{y}\rangle=\min(\left|\arg{\mathbf{x}}-\arg{\mathbf{y}}\right|,2\pi-\left|\arg{\mathbf{x}}-\arg{\mathbf{y}}\right|) $$

注意一下 $\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;
}