凸包模板

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=2005;
 4 int n,tot;
 5 struct point
 6 {
 7     int x,y;
 8     point(int _x=0,int _y=0){x=_x; y=_y;}
 9     point operator -(const point &rhs)const
10     {
11         return point(x-rhs.x,y-rhs.y);
12     }
13 }p[N],cp[N];
14 typedef point vec;
15 int cross(const vec &a,const vec &b)
16 {
17     return (a.x*b.y)-(a.y*b.x);
18 }
19 int dis(point a,point b)
20 {
21     return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
22 }
23 bool cmp(const point &a,const point &b)
24 {
25     int z=cross(a-p[0],b-p[0]);
26     if(z>0||(z==0 && dis(p[0],a)<dis(p[0],b)))
27         return 1;
28     else return 0;
29 }
30 void get_cp()
31 {
32     int k=0;
33     for(int i=0;i<n;i++)
34         if(p[i].y<p[k].y || p[i].y==p[k].y && p[i].x<p[k].x) k=i;
35     swap(p[0],p[k]);
36     sort(p+1,p+n,cmp);
37     tot=2,cp[0]=p[0];cp[1]=p[1];
38     for(int i=2;i<n;i++)
39     {
40         while(tot>1 && cross(cp[tot-2]-cp[tot-1],p[i]-cp[tot-1])>0) tot--;
41         cp[tot++]=p[i];
42     }
43 }
44 int main()
45 {
46     scanf("%d",&n);
47     for(int i=0;i<n;i++) scanf("%d%d",&p[i].x,&p[i].y);
48     get_cp();
49     for(int i=0;i<tot;i++) printf("%d %d
",cp[i].x,cp[i].y);
50     return 0;
51 }