Graham求凸包模板

 1 struct P
 2 {
 3     double x, y;
 4     P(double x=0, double y=0):x(x), y(y) {}
 5     double add(double a, double b){
 6         if(fabs(a+b)<eps*(fabs(a)+fabs(b))) return 0;
 7         return a+b;
 8     }
 9     P operator + (P p){
10         return P(add(x, p.x), add(y, p.y));
11     }
12     P operator - (P p){
13         return P(add(x, -p.x), add(y, -p.y));
14     }
15     P operator *(double d){
16         return P(x*d, y*d);
17     }
18     double dot(P p){                 //点积
19         return add(x*p.x, y*p.y);
20     }
21     double det(P p){                 //差积
22         return add(x*p.y, -y*p.x);
23     }
24 }ps[N];
25 
26 double dist(P a, P b){
27     return sqrt((b-a).dot(b-a));
28 }
29 
30 bool cmp_x(const P& p, const P& q){
31     if(p.x!=q.x) return p.x < q.x;
32     return p.y < q.y;
33 }
34 //返回求得的凸包
35 vector<P> convex_hull(P *ps, int n){
36     sort(ps,ps+n,cmp_x);
37     int k = 0;          //凸包顶点数
38     vector<P> qs(n*2);
39     //构造凸包的下侧
40     for(int i=0; i<n; i++)
41     {
42         while(k>1 && (qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0) k--;
43         qs[k++] = ps[i];
44     }
45     //构造凸包的上侧
46     for(int i=n-2,t=k; i>=0; i--)
47     {
48         while(k>t && (qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0) k--;
49         qs[k++] = ps[i];
50     }
51     qs.resize(k-1);
52     return qs;
53 }