题解：P3442 [POI2006] NAJ-The Invasion

· · 题解

然后快速计算答案。 ![](https://cdn.luogu.com.cn/upload/image_hosting/e7t7abf9.png) 如上图，考虑答案为红点，即为总点数减去蓝点数。 凸包被分成了 $4$ 个部分，其中有 $3$ 个部分都是蓝点。 我们发现每个部分的蓝点是独立的，且只与三角形的一条边有关。 ![](https://cdn.luogu.com.cn/upload/image_hosting/gaboyzf9.png) 考虑计算每条边对应区域的蓝点数。记 $f[i][j] $ 表示位于 $\overrightarrow {P_iP_j}$ 逆时针方向的所有点的权值和。发现若 $P_k$ 位于 $\overrightarrow {P_iP_j}$ 的顺时针方向，则答案单调不降（如上图）。于是我们可以先按照点关于 $P_i$ 的相对位置排序（这个可以用叉积方便地判断），接着再双指针扫一遍即可得到 $f[i]$ 的所有值。 统计答案是简单的，题目中保证了顺时针给定凸包上的点，所以可以直接按序依次枚举。但需要注意如果有位置与凸包顶点重合的点用叉积判断其位置关系可能会炸掉。我们不妨再计算 $f$ 时先不考虑这些点，最后统计答案的时候再单独考虑这些点。 时间复杂度 $O(n^3 + nm\log m)

代码如下（马蜂有点抽象 

#include<bits/stdc++.h>
#define ld  int 
#define pdd pair<ld,ld>
#define pii pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define cmax(a,b) ((a)=max((a),(b)))
using namespace std;
namespace IO{
    const int maxn=(1<<20);char *p1,*p2,buf[maxn];
    #define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,maxn,stdin),p1==p2)?EOF:*p1++)
    int read(){
        int f=1,k=0;char c;
        while(!isdigit(c=gc()))if(c=='-')f=-1;
        while(isdigit(c))k=k*10+c-48,c=gc();
        return f*k;
    }
    void write(int k,char c){
        if(k<0){putchar('-');k=-k;}
        char st[21];int top=0;
        do{st[++top]=(k%10)|48,k/=10;}while(k);
        while(top)putchar(st[top--]);
        putchar(c);
    }
}using namespace IO;
const int N=605,M=1e4+10;
int f[N][N],corner[N],x,y,z,n,m,sum,ans=-0x3f3f3f3f;
pdd P[N],center;map<pdd,int> mp;
struct V{pdd pos;int val;}v[M];
inline int Cross(pdd x,pdd y){
    return (x.fi-center.fi)*(y.se-center.se)-(x.se-center.se)*(y.fi-center.fi);
}
inline bool cmp(V x,V y){return Cross(x.pos,y.pos)<0;}//y位于x的顺时针方向 
inline int nxt(int x){return x==n?1:x+1;}
void pre_solve(int id){
    center=P[id];
    int val=0,l=1;
    sort(v+1,v+1+m,cmp);
    for(int j=nxt(id);j!=id;j=nxt(j)){
        while(l<=m&&Cross(P[j],v[l].pos)>0)val+=v[l++].val;//v[l].pos位于P[j]的逆时针方向  
        f[id][j]=val;
    }
}
int solve(){
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
            for(int k=j+1;k<=n;++k)
                cmax(ans,sum-f[i][j]-f[j][k]-f[k][i]+corner[i]+corner[j]+corner[k]);
    return ans;
}
signed main(){
    n=read();
    for(int i=1;i<=n;++i){
        P[i].fi=read(),P[i].se=read();
        mp[P[i]]=i;
    }
    m=read();
    for(int i=1;i<=m;++i){
        x=read(),y=read(),z=read();
        v[i]={{x,y},z};
        corner[mp[{x,y}]]+=z;
        if(mp[{x,y}])--i,--m;
        else sum+=z;
    }
    for(int i=1;i<=n;++i)pre_solve(i);
    write(solve(),'\n');
    return 0;
}