这是题目。
是一道裸的凸包算法题，但是我一开始还是写WA了。先贴代码
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #define mod 9999973 9 #define N 10000510 using namespace std;11 int n , top;12 double ans;13 struct point14 {15 int x , y;16 bool operator < (const point & a) const17 {18 if(x != a.x) return x < a.x;19 return y < a.y;20 }21 }e[N] , sta[N];22 double get(point p1 , point p2 , point p3)23 {24 return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);25 }26 double dist(point p1 , point p2)27 {28 return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));29 }30 void work()31 {32 scanf("%d", &n);33 for(int i = 1 ; i <= n ; ++i) scanf("%d%d", &e[i].x, &e[i].y);34 sort(e + 1 , e + 1 + n);35 sta[++top] = e[1] , sta[++top] = e[2];36 for(int i = 3 ; i <= n ; ++i)37 {38 while(top >= 2 && get(sta[top] , e[i] , sta[top - 1]) <= 0) --top;39 sta[++top] = e[i];40 }41 int len = top;42 sta[++top] = e[n - 1];43 for(int i = n - 2 ; i >= 1 ; --i)44 {45 while(len != top && get(sta[top] , e[i] , sta[top - 1]) <= 0) --top;46 sta[++top] = e[i];47 }48 ans += dist(sta[1] , sta[top]);49 for(int i = 1 ; i < top ; ++i) ans += dist(sta[i] , sta[i + 1]);50 printf("%.1f", ans);51 }52 int main()53 {54 work();55 return 0;56 }
错误原因：
1、一开始把求叉积的代码写挫了，return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);把(p2.y - p3.y) 写成了(p1.x - p3.x)2、在while循环退栈的过程中，叉积>=0都可以退，不仅仅只是>0，这是关键错误，改了这个程序就过了。
求凸包的方法：
先将所有的点按照x大小排序，x相等就用y来排序。
然后从第三个点开始往后扫，扫到某个点i，求叉积，判断左右。。
第一遍从前往后扫出下凸壳，然后从后往前弄出上凸壳，再求周长就可以了
然后先将第一个点和第二个点入栈(这个很好理解)