凸包
在平面上能包含所有给定点的最小凸多边形叫做凸包。可以理解为用一个橡皮筋围住所有给定点的形态。
凸包是周长最小的能围住所有点的凸多边形。
Andrew 算法
- 将点排序 x 为第一关键字，y 为第二关键字
- 从左向右维护可以得到凸包的上半部分（上凸包），从右向左可以得到凸包的下半部分（下凸包），可以发现，若下一个点在当前边的左侧，则这条边在凸包上，删去，否则保留这条边，然后就可以得到凸包。使用叉积判断下一个点的位置
注意排序，去重
洛谷 P2742 [USACO5.1] 圈奶牛Fencing the Cows /【模板】二维凸包/AcWing 1401. 围住奶牛
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
| #include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct Point{
double x,y;
Point(double a=0,double b=0){
x=a,y=b;
}
Point operator + (const Point a)const{
return Point(x+a.x,y+a.y);
}
Point operator - (const Point a)const{
return Point(x-a.x,y-a.y);
}
Point operator * (const int a)const{
return Point(x*a,y*a);
}
double operator * (const Point a)const{
return x*a.x+y*a.y;
}
friend double cross(Point a,Point b){
return a.x*b.y-a.y*b.x;
}
bool operator < (const Point a)const{
return (x==a.x)?y<a.y:x<a.x;
}
bool operator > (const Point a)const{
return (x==a.x)?y>a.y:x>a.x;
}
bool operator == (const Point a)const{
return x==a.x&&y==a.y;
}
friend double area(Point a,Point b,Point c){
return cross(b-a,c-a);
}
friend double get_dist(Point a,Point b){
return sqrt((b-a)*(b-a));
}
}q[N];
int n;
int stk[N],top;
double andrew(){
sort(q,q+n);
n=unique(q,q+n)-q;
top=0;
for(int i=0;i<n;i++){
while(top>=2&&area(q[stk[top-1]],q[stk[top]],q[i])>=0){
top--;
}
stk[++top]=i;
}
for(int i=n-1;i>=0;i--){
if(q[stk[top]]==q[i])continue;
while(top>=2&&area(q[stk[top-1]],q[stk[top]],q[i])>0){
top--;
}
stk[++top]=i;
}
double res=0;
for(int i=2;i<=top;i++){
res+=get_dist(q[stk[i-1]],q[stk[i]]);
}
return res;
}
int main(){
cin >> n;
for(int i=0;i<n;i++){
cin >> q[i].x >> q[i].y;
}
double res=andrew();
cout << fixed << setprecision(2) << res;
return 0;
}
|