题解 bzoj2564 【集合的面积】

传送门

题面的定义显然就是求一个点集 $A,B$A,B的闵可夫斯基和的凸包的面积的两倍。

那么这道题就是闵可夫斯基和的模板了。

所谓闵可夫斯基和，即给你两个点集 $A,B$A,B，求一个点集 $C=\{x+y\mid x\in A,y\in B\}$C={x+y ∣ x∈A,y∈B}， $C$C即点集 $A,B$A,B的闵可夫斯基和。

对于求闵可夫斯基和，我的理解是：我们考虑先求 $A,B$A,B的凸包，闵可夫斯基和的凸包肯定是由 $A,B$A,B凸包上的点加起来的，我们对于 $A,B$A,B的两个凸包，存的时候按点坐标从最左下角然后逆时针方向存。

因为 $A,B$A,B两个凸包的点是按逆时针存的，所以我们通过瞪眼法可以发现，如果把闵可夫斯基和的凸包上的点用一个 $n\times m$n×m的矩阵表示 $(n,m$(n,m是凸包 $A,B$A,B上点的个数 $)$)， $(i,j$(i,j表示凸包 $A$A上的第 $i$i个点加上凸包 $B$B上的第 $j$j个点 $)$)那么闵可夫斯基和的凸包上的点是从左下角 $(1,1)$(1,1)到右上角 $(n,m)$(n,m)的一条路径 $($(需要意会 $)$)。然后我们两个指针分别指向 $A,B$A,B的两个凸包，每次取出两个点比较，利用叉积看谁往外偏的多就选谁。

觉得还是代码好理解，反正我是直接看代码看懂的：

void minkowski(){
    for(int i=1;i<cnt1;i++) va[i]=tu[0][i+1]-tu[0][i];va[cnt1]=tu[0][1]-tu[0][cnt1];
    for(int i=1;i<cnt2;i++) vb[i]=tu[1][i+1]-tu[1][i];vb[cnt2]=tu[1][1]-tu[1][cnt2];
    int i1=1,i2=1;
    tot=0;
    ans[++tot]=tu[0][1]+tu[1][1];
    while(i1<=cnt1&&i2<=cnt2){
        if(cross(va[i1],vb[i2])>=0) ans[tot+1]=ans[tot]+va[i1++];
        else ans[tot+1]=ans[tot]+vb[i2++];
        tot++;
    }
    while(i1<=cnt1){
        ans[tot+1]=ans[tot]+va[i1++];
        tot++;
    }
    while(i2<=cnt2){
        ans[tot+1]=ans[tot]+vb[i2++];
        tot++;
    }
}

$tu\left[0/1\right]$tu[0/1]是 $A,B$A,B的两个凸包上的点，用 $va,vb$va,vb存凸包上点变化的向量，那么后面通过向量加法就可以表示凸包上点的变化。

剩下就是凸包，叉积等板子，最后求面积的话其实不用再求一遍闵可夫斯基和的凸包 $($(我无聊又求了一遍 $)$)，如果求的话作用就是去掉凸包上三点共线的点：

#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define ll long long
#define hh puts("")
using namespace std;
int n,m,st[100005],top,cnt1,cnt2,cnt,tot;
ll res;
double eps=1e-8;
struct point{
    ll x,y;
}a[100005],b[100005],tu[2][100005],va[100005],vb[100005],ans[200005],ed[200005];
inline int read(){
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-1;ch=getchar();}
    while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
    return ret*ff;
}
point operator + (point A,point B){
    return (point){A.x+B.x,A.y+B.y};
}
point operator - (point A,point B){
    return (point){A.x-B.x,A.y-B.y};
}
inline bool cmp(point A,point B){
    return A.x==B.x?A.y<B.y:A.x<B.x;
}
inline double getk(point A,point B){
    if(fabs(double(A.x-B.x))<eps) return 1e20;
    return (double)(B.y-A.y)/(double)(B.x-A.x);
}
inline ll cross(point A,point B){
    return (ll)A.x*B.y-(ll)A.y*B.x;
}
void Graham(point t[],int id,int all){
    cnt=top=0;
    for(int i=1;i<=all;i++){
        st[++top]=i;
        while(top>=3&&getk(t[i],t[st[top-2]])<=getk(t[st[top-1]],t[st[top-2]])){
            st[top-1]=st[top];
            top--;
        }
    }
    for(int i=1;i<=top;i++) tu[id][++cnt]=t[st[i]];
    top=0;
    for(int i=1;i<=all;i++){
        st[++top]=i;
        while(top>=3&&getk(t[i],t[st[top-2]])>=getk(t[st[top-1]],t[st[top-2]])){
            st[top-1]=st[top];
            top--;
        }
    }
    for(int i=top-1;i>=2;i--) tu[id][++cnt]=t[st[i]];
}
void minkowski(){
    for(int i=1;i<cnt1;i++) va[i]=tu[0][i+1]-tu[0][i];va[cnt1]=tu[0][1]-tu[0][cnt1];
    for(int i=1;i<cnt2;i++) vb[i]=tu[1][i+1]-tu[1][i];vb[cnt2]=tu[1][1]-tu[1][cnt2];
    int i1=1,i2=1;
    tot=0;
    ans[++tot]=tu[0][1]+tu[1][1];
    while(i1<=cnt1&&i2<=cnt2){
        if(cross(va[i1],vb[i2])>=0) ans[tot+1]=ans[tot]+va[i1++];
        else ans[tot+1]=ans[tot]+vb[i2++];
        tot++;
    }
    while(i1<=cnt1){
        ans[tot+1]=ans[tot]+va[i1++];
        tot++;
    }
    while(i2<=cnt2){
        ans[tot+1]=ans[tot]+vb[i2++];
        tot++;
    }
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();
    for(int i=1;i<=m;i++) b[i].x=read(),b[i].y=read();
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+m+1,cmp);
    Graham(a,0,n);
    cnt1=cnt;
    Graham(b,1,m);
    cnt2=cnt;
    minkowski();
    tot--;
    sort(ans+1,ans+tot+1,cmp);
    top=cnt=0;
    for(int i=1;i<=tot;i++){
        st[++top]=i;
        while(top>=3&&getk(ans[i],ans[st[top-2]])<=getk(ans[st[top-1]],ans[st[top-2]])){
            st[top-1]=st[top];
            top--;
        }
    }
    for(int i=1;i<=top;i++) ed[++cnt]=ans[st[i]];
    top=0;
    for(int i=1;i<=tot;i++){
        st[++top]=i;
        while(top>=3&&getk(ans[i],ans[st[top-2]])>=getk(ans[st[top-1]],ans[st[top-2]])){
            st[top-1]=st[top];
            top--;
        }
    }
    for(int i=top-1;i>=2;i--) ed[++cnt]=ans[st[i]];
    for(int i=1;i<cnt;i++) res+=cross(ed[i],ed[i+1]);
    res+=cross(ed[cnt],ed[1]);
    printf("%lld",res);
    return 0;
}