求凸包（两遍扫描，求上下凸包的方法）

求凸包模版

struct point { double x,y; double val,len; }points[20]; point points1[20]; point points2[20]; const int INF=1e8; bool cmp(point a,point b) { if(a.x==b.x) return a.y<b.y; return a.x<b.x; } double chaji(point a,point b,point c,point d) { return (b.x-a.x)*(d.y-c.y)-(b.y-a.y)*(d.x-c.x); } int real[20]; int cover(int potnum) { sort(points1,points1+potnum,cmp); int ansnum=0; for(int i=0;i<potnum;i++) { while(ansnum>1&&chaji(points2[ansnum-2],points2[ansnum-1],points2[ansnum-1],points1[i])<0) ansnum--; points2[ansnum++]=points1[i]; } int k=ansnum; for(int i=potnum-2;i>=0;i--) { while(ansnum>k&&chaji(points2[ansnum-2],points2[ansnum-1],points2[ansnum-1],points1[i])<0) ansnum--; points2[ansnum++]=points1[i]; } if(potnum>1) ansnum--; return ansnum; } double way(point a,point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }

 

转载于:https://www.cnblogs.com/wsruning/p/5703112.html

总结

以上是生活随笔为你收集整理的求凸包（两遍扫描，求上下凸包的方法）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。