什么是凸包，簡單來說就是一個凸多邊形，
場景
現在有一些點，讓你畫一個包含所有點的圈，要求圖形的周長最短，很明顯，用這些點上的一部分點作為節點連城直線是最短的，而最后的圖形就是一個凸多邊形，
我們如何來找到凸多邊形上的點，第一我們可以發現最邊緣的點一定位于最后的凸包上，例如y值最小（最大），x值最小（最大）的點，我們可以利用這些點作為我們構造凸包的起點，
首先，對所有點進行排序，找到y值最小的點，如果存在多組y相同，取最左邊的點，
找到起點之后，進行極角排序，就是數學上的比較直線的斜率值（k），顯然, arctan(k) 就是到x軸的角度，起點與其他的點連線求出角度值，從小到大排序，排序出的第一個點很顯然也在凸包上，因為不存在更右的點，
還可以用叉積的方法去判斷是否在左在右，
1 double cross(ff a,ff b,ff c) 2 { 3 return (b.x - a.x)*(c.y-a.y)-(c.x - a.x)*(b.y - a.y); 4 } 5 bool cmp(ff a,ff b) 6 { 7 double m = cross(f[0],a,b); 8 if(m>0) 9 return 1; 10 if(m==0&&dis(f[0],a)-dis(f[0],b)<=0) 11 return 1; 12 return 0; 13 }//用叉積去判斷順序，如果m==0,說明兩點在同一直線上，則距離近的排在前面
用排好的點一個個判斷是不是凸包上的點，現在我們有兩個陣列，一個g陣列存放凸包上的點，一個f陣列放排好序的點，
剛開始時，g陣列上有兩個點，起點和排序后的第一個點，現在點是否屬于凸包，
設定一個cnt值，指向g陣列的尾節點，
如果下一個點于g[cnt]的連線相對g[cnt]和g[cnt-1]的連線偏左，該點加入g陣列，cnt++;
如果偏右，cnt--,該點繼續重復比較的步驟，直到找到相對偏左的點（該程序相當于就是刪去s陣列凸包內的點）
當最后一個點判斷完成后，g陣列就儲存了從起點逆時針一圈凸包上的點
求凸包的周長
順序列舉g陣列上的點累加dis(g[i],g[i+1]),最后再加上dis(g[cnt],g[0])
完整代碼
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 using namespace std; 7 struct ff 8 { 9 double x,y; 10 bool operator < (ff b)const 11 { 12 if(y == b.y) 13 return x<b.x; 14 return y<b.y; 15 } 16 }f[100005],g[100008];double xx,yy; 17 double dis(ff a,ff b) 18 { 19 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 20 } 21 double cross(ff a,ff b,ff c) 22 { 23 return (b.x - a.x)*(c.y-a.y)-(c.x - a.x)*(b.y - a.y); 24 }//求叉積 25 bool cmp(ff a,ff b) 26 { 27 double m = cross(f[0],a,b); 28 if(m>0) 29 return 1; 30 if(m==0&&dis(f[0],a)-dis(f[0],b)<=0) 31 return 1; 32 return 0; 33 } 34 int main() 35 { 36 int n; 37 scanf("%d",&n); 38 for ( int i = 0;i<n;++i) scanf("%lf%lf",&f[i].x,&f[i].y); 39 sort(f,f+n);//找到最左最下的點 40 if(n == 1) 41 printf("%.2f\n",0.00); 42 else if(n == 2) 43 printf("%.2f\n",dis(f[0],f[1])); 44 else 45 { 46 g[0] = f[0];//凸包陣列放入起點 47 xx = g[0].x; 48 yy = g[0].y; 49 sort(f+1,f+n,cmp);//極角排序 50 g[1] = f[1];//第二個點也在凸包內 51 int cnt = 1;//指向凸包陣列的尾結點 52 for(int i = 2;i<n;++i) 53 { 54 while(i>=1&&cross(g[cnt-1],g[cnt],f[i])<0) 55 cnt--;//如果新加進來的節點相對最后兩點連線偏右，減去最后一個點，回圈判斷 56 g[++cnt] = f[i];//加入新節點 57 } 58 double s = 0; 59 60 for (int i = 1;i<=cnt;++i) 61 s+=dis(g[i-1],g[i]); 62 s+=dis(g[cnt],f[0]);//計算每條邊的長度 63 printf("%.2lf",s); 64 } 65 return 0; 66 }View Code
題目：https://www.luogu.com.cn/problem/P2742
借鑒：https://www.cnblogs.com/aiguona/p/7232243.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/152959.html
標籤：其他
上一篇：本地儲存