P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二維凸包

題目：

給定一些點(diǎn)，問(wèn)圍住所有點(diǎn)所用的圍欄的長(zhǎng)度

題解：

凸包模板題
凸包詳細(xì)

代碼：

#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> using namespace std; int n; struct point {double x,y; }p[10005],s[10005]; double check(point a1,point a2,point b1,point b2)//檢查叉積是否大于0，如果是a就逆時(shí)針轉(zhuǎn)到b {return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y); } double d(point p1,point p2)//兩點(diǎn)間距離。。。 {return sqrt((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x)); } bool cmp(point p1,point p2)//排序函數(shù)，這個(gè)函數(shù)別寫錯(cuò)了，要不然功虧一簣 {double tmp=check(p[1],p1,p[1],p2);if(tmp>0) return 1;if(tmp==0&&d(p[0],p1)<d(p[0],p2)) return 1;return 0; } int main() {scanf("%d",&n);double mid;for(int i=1;i<=n;i++){scanf("%lf%lf",&p[i].x,&p[i].y);if(i!=1&&p[i].y<p[1].y)//這是是去重 {mid=p[1].y;p[1].y=p[i].y;p[i].y=mid;mid=p[1].x;p[1].x=p[i].x;p[i].x=mid;}} sort(p+2,p+1+n,cmp);//系統(tǒng)快排 s[1]=p[1];//最低點(diǎn)一定在凸包里 int cnt=1;for(int i=2;i<=n;i++){while(cnt>1&&check(s[cnt-1],s[cnt],s[cnt],p[i])<=0) //判斷前面的會(huì)不會(huì)被踢走，如果被踢走那么出棧cnt--;s[++cnt]=p[i];}s[cnt+1]=p[1];//最后一個(gè)點(diǎn)回到凸包起點(diǎn)double ans=0; for(int i=1;i<=cnt;i++) ans+=d(s[i],s[i+1]);//然后s里存好了凸包序列，只需要把兩兩距離累加就行printf("%.2lf\n",ans);return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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