求凸包模版

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)); }

?

轉(zhuǎn)載于:https://www.cnblogs.com/wsruning/p/5703112.html

總結(jié)

以上是生活随笔為你收集整理的求凸包（两遍扫描，求上下凸包的方法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。