题解：P12764 [POI 2018 R3] 两个棋子 Two stones

· · 题解

Solution

和 这道题 几乎一模一样。

问题转化为：给你一组向量 a，请你分配一个权值 w_i \in \{-1,0,1\}，最大化 |\sum w_ia_i| 的值。

设最终的向量和是 v。

显然不存在和 v 垂直的向量。和它夹角小于 90 度的选上一定更优，大于 90 度的选相反数一定更优。

结论也和那道题一模一样了，极角排序之后跑一个双指针即可。注意特判向量贡献的情况（需要算出是同向还是反向。）

#include<bits/stdc++.h>
#define int long long 
#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=200000+10;
int n,x[MAXN],y[MAXN];
int gid(pair<int,int> p) {
    if(p.first>0&&p.second>=0) return 1;
    if(p.first<=0&&p.second>0) return 2;
    if(p.second<=0&&p.first<0) return 3;
    return 4;
}
int solve(int sx,int sy,int tx,int ty) {
    int px=sx-tx,py=sy-ty;
    tx-=px,ty-=py;
    return tx*tx+ty*ty;
}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    vector<pair<int,int>> vc;
    ffor(i,1,n) {
        cin>>x[i]>>y[i];
        if(x[i]!=0||y[i]!=0) vc.push_back({x[i],y[i]});
    }
    sort(vc.begin(),vc.end(),[](pair<int,int> A,pair<int,int> B) {
        if(gid(A)!=gid(B)) return gid(A)<gid(B);
        return A.first*B.second>A.second*B.first;
    });
    n=vc.size();
    ffor(i,1,n) x[i]=vc[i-1].first,y[i]=vc[i-1].second;
    int pos=1,sx=0,sy=0,tx=0,ty=0,ans=0;
    ffor(i,1,n) sx+=x[i],sy+=y[i];
    tx=x[1],ty=y[1];
    ans=max(ans,sx*sx+sy*sy);
    ffor(i,1,n) {
        ans=max(ans,solve(sx,sy,tx,ty));
        if(x[i]*y[i%n+1]-y[i]*x[i%n+1]<0||x[i]*y[i%n+1]-y[i]*x[i%n+1]<0&&(x[i]*x[i%n+1]<0||y[i]*y[i%n+1]<0)) {pos=i%n+1,tx=x[pos],ty=y[pos];continue ;}
        while(pos%n+1!=i&&(x[i]*y[pos%n+1]-y[i]*x[pos%n+1]>0||x[i]*y[pos%n+1]-y[i]*x[pos%n+1]==0&&x[i]*x[pos%n+1]>=0&&y[i]*y[pos%n+1]>=0)) {
            pos=pos%n+1;
            tx+=x[pos],ty+=y[pos],ans=max(ans,solve(sx,sy,tx,ty));
        }
        tx-=x[i],ty-=y[i],ans=max(ans,solve(sx,sy,tx,ty));
    }
    cout<<ans; 
    return 0;
}