题目描述

　　对于一个平面上点的集合P={(xi,yi )}，定义集合P的面积F(P)为点集P的凸包的面积。

　　对于两个点集A和B，定义集合的和为：

　　A+B={(xiA+xjB,yiA+yjB ):(xiA,yiA )∈A,(xjB,yjB )∈B}

　　现在给定一个N个点的集合A和一个M个点的集合B，求2F(A+B)。

 

---

输入格式

　第一行包含用空格隔开的两个整数，分别为N和M；

　　第二行包含N个不同的数对，表示A集合中的N个点的坐标；

　　第三行包含M个不同的数对，表示B集合中的M个点的坐标。

　

---

输出格式

　一共输出一行一个整数，2F(A+B)。

---

 

数据规模和约定　　对于30%的数据满足N ≤ 200，M ≤ 200；　　对于100%的数据满足N ≤ 10^5，M ≤ 10^5，|xi|, |yi| ≤ 10^8。

---

• 题解：

  • 如果一个点成为了和$A+B$的凸包，那么一定同时在$A$和$B$的凸包上;
  • 设$A+B$看成把凸包$A$平移后放在凸包$B$上，发现在两个凸包上组合成新的凸包的点对是单调的；
  • 类似$graham$维护两个指针；
  • 不太好说，附图，但是建议自己$YY$：
    

     

  • 1 #include
              
                2 #define ll long long  3 using namespace std; 4 const int N=200010; 5 int n,m,cnt1,cnt2,Cnt; 6 char gc(){ 7     static char*p1,*p2,s[1000000]; 8     if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin); 9     return (p1==p2)?EOF:*p1++;10 }11 int rd(){12     int x=0,f=1; char c=gc();13     while(c<'0'||c>'9'){
            if(c=='-')f=-1;c=gc();}14     while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=gc();}15     return x*f;16 }17 struct poi{18     int x,y;19     poi(int _x=0,int _y=0):x(_x),y(_y){};20     poi operator +(const poi&A)const{
            return poi(x+A.x,y+A.y);}21     poi operator -(const poi&A)const{
            return poi(x-A.x,y-A.y);}22     bool operator <(const poi&A)const{
            return x==A.x?y
               
                
                 1 && crs(q[cnt]-q[cnt-1],p[i]-q[cnt])<=0)cnt--;31         q[++cnt]=p[i];32     }33     int now=cnt;34     for(int i=tot-1;i;i--){35         while(cnt>now && crs(q[cnt]-q[cnt-1],p[i]-q[cnt])<=0)cnt--;36         q[++cnt]=p[i];37     }38     cnt--;39 }40 int main(){41     #ifndef ONLINE_JUDGE42     freopen("bzoj2564.in","r",stdin);43     freopen("bzoj2564.out","w",stdout);44     #endif45     n=rd();m=rd();46     for(int i=1;i<=n;i++)p1[i].x=rd(),p1[i].y=rd();47     for(int i=1;i<=m;i++)p2[i].x=rd(),p2[i].y=rd();48     convex(p1,q1,n,cnt1);49     convex(p2,q2,m,cnt2);50     int i,j;51     for(i=1,j=1;i<=cnt1;i++){52         Q[++Cnt]=q1[i]+q2[j];53         while(j<=cnt2&&crs(q2[j+1]-q2[j],q1[i+1]-q1[i])>0){54             Q[++Cnt]=q1[i]+q2[++j];55         }56     }57     for(;j<=cnt2+1;j++)Q[++Cnt]=q1[i]+q2[j];58     Cnt--;59     ll ans=0;60     for(i=2;i