凸包

思路

  • 取最左边的点x为第一个点,其他所有点根据与点x连线的斜率排序,然后依次扫过去。
  • 如下图所示,线段ab相对于xa按逆时针旋转,所以a在当前确定的凸包集合中;
  • 线段bc相对于ab按顺时针方向旋转,所以b不在当前确定的凸包集合中;
  • 判断两向量的相对旋转方向可以用叉积来计算。a x b > 0 时b相对a逆时针旋转, a x b < 0 时b相对a顺时针旋转

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>
#define INIT(a,b) memset(a,b,sizeof(a))
#define LL long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e4+7;
const int mod=1e9+7;
const double eps = 1e-8,pi=3.14159265;
// 若 一点的坐标在前面两点的右边,则更新右端点
int n;
int dcmp(double x) // 三态函数 ,在下面用于是否在精度
{
if(fabs(x)<eps)return 0;
else return x>0?1:-1;
}
struct Point
{
double x,y;
inline Point(double x=0,double y=0):x(x),y(y){}
}p[N],ch[N];

bool myCmp(Point A,Point B){
if(A.x!=B.x)return A.x<B.x;
else return A.y<B.y;
}
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);
}
bool operator == (const Point& A,const Point& B){
return dcmp(A.x-B.x)==0&&dcmp(A.y-B.y)==0;
}
inline double Cross(Point A,Point B) // 计算叉积
{
return A.x * B.y - A.y * B.x;
}
int ConvexHull()
{
sort(p,p+n,myCmp);
int m=0;
for(int i=0;i<n;i++){
// 求下曲包,当该点在前进方向的右边时(使用叉积判断),删除前进的右端点,
// 循环,直到不在,并将该点加入,不在右边,则直接加入
while(m>1&&dcmp(Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]))<=0)m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-2;i>=0;i--){ // 因 pn-1 已经遍历过,故从n-2开始
// 求上凸包,最终形成合围,为完整凸包
while(m>k&&dcmp(Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]))<=0)m--;
ch[m++]=p[i];
}
if(n>1)m--; // 因要形成凸包,故起始点重复,减1
return m; //返回顶点个数
}
double Dis(Point A,Point B){
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
int main(){
int m;
cin >> n;
for(int i=0;i<n;i++){
int a,b;
cin >> a >> b;
p[i]=Point(a,b);
}
m=ConvexHull();

//计算凸包周长
/* double ans=0.0;
for(int i=0;i<m-1;i++)
ans+=Dis(ch[i],ch[i+1]);
ans+=Dis(ch[m-1],ch[0]);
printf("%.1f\n",ans);*/

// 计算凸包面积
double ans=0.0;
ch[m]=ch[0];
for(int i=0;i<m;i++){
ans+=(ch[i].x*ch[i+1].y-ch[i+1].x*ch[i].y);
}
ans=ans/2;
printf("%.0f\n",floor(ans/50));
return 0;
}

}
/*
10
11
1 -1
1 1
1 2
2 -1
2 0
2 3
3 -2
3 2
4 1
4 3
5 0

output 15.0
*/
Donate comment here