凸包是啥？？

凸包就是：

給定二維平面上的點(diǎn)集，凸包就是將最外層的點(diǎn)連接起來(lái)構(gòu)成的凸多邊型，它能包含點(diǎn)集中所有的點(diǎn)。

外層的紅線　就是凸包

一般題目會(huì)讓你求利用最外層凸包的一些性質(zhì)如下面這道題

來(lái)看一道模板題：ＨＤＵ　－　１３４８

本題題目就是要求盡可能少的圍墻周長(zhǎng) 圍墻內(nèi)的城堡是多邊形的 而圍墻還要和城堡相隔l距離

可證 實(shí)質(zhì)周長(zhǎng)其實(shí)就是 城堡的凸包周長(zhǎng) + 以l為半徑的周長(zhǎng)之和?

由于多邊形城堡 盡可能少的包圍他其實(shí)就是凸包周長(zhǎng) 而在凸包的拐角處 要相隔l距離 所以變成了一個(gè)圓弧

把圓弧加起來(lái)就是圓的周長(zhǎng)?

n邊形的內(nèi)角和公式 ：（n-2）*180

n變形外角永遠(yuǎn)是360度

所以 可以列式 n×360 - (n-2)×180 -９０×n×２ = 360° （n個(gè)角 減去內(nèi)角 在減去多余的90° 畫(huà)個(gè)圖就能得到）

所以多出來(lái)的那些空間可知就是一個(gè)360°的整圓

關(guān)于這個(gè)方法就是先取左下點(diǎn)為基準(zhǔn)點(diǎn)?

?然后 對(duì)其他點(diǎn) 按照從基準(zhǔn)點(diǎn)的x軸逆時(shí)針?lè)较蛏涑龅臉O角 掃過(guò)的順序排序?

然后再對(duì)其中的每前后三個(gè)點(diǎn)進(jìn)行叉乘操作

?

?如果我們以逆時(shí)針?lè)较虮闅v所有點(diǎn)

ｎ，ｍ，ｌ三個(gè)點(diǎn)　

ｎ為起點(diǎn)　向ｍ和ｌ點(diǎn)做兩個(gè)向量分別是向量ａ，向量ｂ

向量a*b<0 說(shuō)明 a在 b的逆時(shí)針?lè)较?　即是說(shuō)　ｍ點(diǎn)在ｌ點(diǎn)里面，左邊　若選凸包 我們舍棄a的終點(diǎn)ｍ 而選取b的終點(diǎn)?

若叉乘結(jié)果>0說(shuō)明ａ在ｂ的順時(shí)針?lè)较颉∫簿褪恰?#xff4d;在ｌ的外邊　右邊

最終將保存下來(lái)的點(diǎn)　按順序遍歷求兩點(diǎn)之間的線段長(zhǎng)度就可以了

code

#include<bits/stdc++.h>using namespace std; typedef long long ll; const int maxn = 1010; const double pi = acos(-1.0);// 得到PI struct node {double x,y; }p[1010],P[1010];//P內(nèi)存儲(chǔ)凸包內(nèi)的店 int t,tot,N; double L; double X(node a,node b,node c) {return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y); }// 計(jì)算叉積 double len(node a,node b) {return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y)); }//兩點(diǎn)之間距離公式 bool cmp(node b,node c) {double pp = X(p[1],b,c);if(pp<0)return 0;else if(pp>0)return 1;else if(pp==0&&len(p[1],b)<len(p[1],c))return 1;else return 0; }//掃描排序 int main() {scanf("%d",&t);for(int cas = 1;cas<=t;cas++){if(cas!=1)puts("");scanf("%d%lf",&N,&L);for(int i=1;i<=N;i++)scanf("%lf%lf",&p[i].x,&p[i].y);double ans = pi*2.0*L;for(int i=2;i<=N;i++){if(p[1].y>p[i].y)swap(p[1],p[i]);else if(p[1].y==p[i].y&&p[1].x>p[i].x)swap(p[1],p[i]);}//找基準(zhǔn)點(diǎn)sort(p+2,p+1+N,cmp);P[1]=p[1];P[2]=p[2];tot=2;for(int i=3;i<=N;i++){while(tot>1&&X(P[tot-1],P[tot],p[i])<=0)tot--;tot++;P[tot] = p[i];}//篩選點(diǎn)for(int i=1;i<tot;i++){ans+=len(P[i],P[i+1]);}//圍圈求和ans+=len(P[1],P[tot]);printf("%.0lf\n",ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的二维凸包 Graham's Scan的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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