凸包模板水平序的Graham-Scan

该算法的功能是：

对n个无序的点p[]求凸包，结果在s[0~top-1]内。

作为O(nlgn)的算法，已然到达其下界，实现也不复杂。

分析详见黑书。

 1 #include<map>
 2 #include<set>
 3 #include<list>
 4 #include<cmath>
 5 #include<ctime>
 6 #include<queue>
 7 #include<stack>
 8 #include<cctype>
 9 #include<cstdio>
10 #include<string>
11 #include<vector>
12 #include<cstdlib>
13 #include<cstring>
14 #include<iostream>
15 #include<algorithm>
16 #define MAXN 1005
17 #define INF 0x3f3f3f3f
18 #define LL long long
19 #define DBL double
20 #define eps 1e-6
21 #define PI acos(-1.0)
22 #define Test() cout<<"Test"<<endl;
23 #define Debug(a) cout<<#a<<" = "<<a<<endl;
24 #define Debug2(a,b) cout<<#a<<" = "<<a<<" , "<<#b<<" = "<<b<<endl;
25 using namespace std;
26 
27 struct P{
28     DBL x, y;
29 };
30 int n, L;
31 P p[MAXN];
32 
33 bool cmp(P a, P b){
34     return a.y<b.y || (a.y==b.y && a.x<b.x);
35 }
36 DBL mul(DBL t){
37     return t*t;
38 }
39 DBL dis(P a, P b){
40     return sqrt(mul(a.x-b.x)+mul(a.y-b.y));
41 }
42 int dblcmp(DBL x){
43     return fabs(x)<eps? 0: x>0? 1: -1;
44 }
45 DBL cross(P a, P b, P c){        //ab X ac
46     return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
47 }
48 DBL grahamScan(){                //水平序 
49     sort(p, p+n, cmp);
50     int top=-1, s[MAXN], tmp;
51     s[++top]=0, s[++top]=1; 
52     for(int i=2; i<n; i++){        // 做右链
53         while(top>0 && dblcmp(cross(p[s[top-1]], p[s[top]], p[i])) <= 0) top --;
54         s[++top] = i;
55     }
56     tmp = top;                    // 此时的栈顶元素一定是第n个点
57     s[++top]=n-2;
58     for(int i=n-3; i>=0; i--){    // 做左链
59         while(top>tmp && dblcmp(cross(p[s[top-1]], p[s[top]], p[i])) <= 0) top --;
60         s[++top] = i;
61     }                            // 此时的栈顶元素一定是第1个点,即s[top]=s[0]
62     // s[0~top-1]即为所求凸包 
63     DBL res=0;
64     for(int i=0; i<top; i++)
65         res += dis(p[s[i]], p[s[i+1]]);
66     return res+2*PI*L;
67 }
68 
69 int main(){
70     while(cin >> n >> L){
71         for(int i=0; i<n; i++)
72             scanf("%lf%lf", &p[i].x, &p[i].y);
73         printf("%d
", (int)(grahamScan()+0.5));      //+0.5      
74     }
75     return 0;
76 }

View Code

凸包模板 水平序的Graham-Scan

凸包模板水平序的Graham-Scan