bzoj2564 集合的面积

Description

　　对于一个平面上点的集合P={(x_i,y_i )}，定义集合P的面积F(P)为点集P的凸包的面积。
　　对于两个点集A和B，定义集合的和为：
　　A+B={(x_i^A+x_j^B,y_i^A+y_j^B ):(x_i^A,y_i^A )∈A,(x_j^B,y_j^B )∈B}
　　现在给定一个N个点的集合A和一个M个点的集合B，求2F(A+B)。

Input

　第一行包含用空格隔开的两个整数，分别为N和M；
　　第二行包含N个不同的数对，表示A集合中的N个点的坐标；
　　第三行包含M个不同的数对，表示B集合中的M个点的坐标。

Output

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

Sample Input

4 5
0 0 2 1 0 1 2 0
0 0 1 0 0 2 1 2 0 1

Sample Output

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

正解：$Minkowski$和。

$Minkowski$和，就是题面的这个东西。。

分别求出两个点集的凸包，然后贪心地加点就行。

首先，$A$凸包和$B$凸包的第一个点的和肯定会在最终的凸包里。

然后我们设$A$凸包到了$i$点，$B$凸包到了$j$点。

如果$a[i+1]+b[j]$比$a[i]+b[j+1]$更凸，那么就用$A$凸包更新，否则用$B$凸包更新。

最后求出的这个就是新凸包，直接用叉积算面积就行了。

 1 #include <bits/stdc++.h>
 2 #define il inline
 3 #define RG register
 4 #define ll long long
 5 #define N (500010)
 6  
 7 using namespace std;
 8  
 9 struct point{
10   ll x,y;
11   il point operator + (const point &a) const{
12     return (point){x+a.x,y+a.y};
13   }
14   il point operator - (const point &a) const{
15     return (point){x-a.x,y-a.y};
16   }
17 }p[N],t1[N],t2[N],st[N];
18  
19 int n,m,top;
20 ll S;
21  
22 il int gi(){
23   RG int x=0,q=1; RG char ch=getchar();
24   while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
25   if (ch=='-') q=-1,ch=getchar();
26   while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
27   return q*x;
28 }
29  
30 il int cmp(const point &a,const point &b){
31   if (a.x==b.x) return a.y<b.y; return a.x<b.x;
32 }
33  
34 il ll cross(RG point a,RG point b){ return a.x*b.y-a.y*b.x; }
35  
36 il void graham(point *p,point *t,RG int n){
37   sort(p+1,p+n+1,cmp);
38   for (RG int i=1;i<=n;++i){
39     while (top>=2 && cross(p[i]-t[top-1],t[top]-t[top-1])>=0) --top;
40     t[++top]=p[i];
41   }
42   for (RG int i=n-1,la=top;i>=1;--i){
43     while (top>la && cross(p[i]-t[top-1],t[top]-t[top-1])>=0) --top;
44     t[++top]=p[i];
45   }
46   --top; return;
47 }
48  
49 int main(){
50 #ifndef ONLINE_JUDGE
51   freopen("area.in","r",stdin);
52   freopen("area.out","w",stdout);
53 #endif
54   n=gi(),m=gi();
55   for (RG int i=1;i<=n;++i) p[i].x=gi(),p[i].y=gi(); graham(p,t1,n),n=top,top=0;
56   for (RG int i=1;i<=m;++i) p[i].x=gi(),p[i].y=gi(); graham(p,t2,m),m=top,top=0;
57   st[top=1]=t1[1]+t2[1];
58   for (RG int i=1,j=1;i<=n || j<=m;){
59     RG point x=t1[(i-1)%n+1]+t2[j%m+1],y=t1[i%n+1]+t2[(j-1)%m+1];
60     if (cross(x-st[top],y-st[top])>=0) st[++top]=x,++j; else st[++top]=y,++i;
61   }
62   for (RG int i=2;i<top;++i) S+=cross(st[i]-st[1],st[i+1]-st[1]); cout<<S; return 0;
63 }