http://acm.hust.edu.cn/vjudge/contest/view.action?cid=28417#problem/E

題目大意：依次給n個(gè)點(diǎn)圍成的一個(gè)城堡，在周?chē)▏鷫?#xff0c;要求圍墻離城墻的距離大于一定的值，求圍墻最短長(zhǎng)度（結(jié)果四舍五入

解題思路：求圍住所有點(diǎn)的凸包周長(zhǎng)+一個(gè)圓的周長(zhǎng)

#include<iostream> #include<cmath> #include<string.h> #include<string> #include<stdio.h> #include<algorithm> #include<iomanip>using namespace std; #define eps 0.0000000001 #define PI acos(-1.0)//******************************************************************************* //點(diǎn)和向量 struct Point{double x,y;Point(double x=0,double y=0):x(x),y(y){} }; typedef Point Vector; Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);} bool operator<(const Vector& a,const Vector& b){return a.x<b.x||(a.x==b.x && a.y<b.y);} int dcmp(double x){if(fabs(x)<eps)return 0;else return x<0 ? -1:1; } double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}//向量點(diǎn)積 double Length(Vector A){return sqrt(Dot(A,A));}//向量模長(zhǎng) double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;} //******************************************************************************** //計(jì)算凸包輸入點(diǎn)數(shù)組p，個(gè)數(shù)n，輸出點(diǎn)數(shù)組ch，返回凸包定點(diǎn)數(shù) //輸入不能有重復(fù)，完成后輸入點(diǎn)順序被破壞 //如果不希望凸包的邊上有輸入點(diǎn)，把兩個(gè)<=改成< //精度要求高時(shí)，建議用dcmp比較 //基于水平的Andrew算法-->1、點(diǎn)排序2、刪除重復(fù)的然后把前兩個(gè)放進(jìn)凸包 //3、從第三個(gè)往后當(dāng)新點(diǎn)在凸包前進(jìn)左邊時(shí)繼續(xù)，否則一次刪除最近加入的點(diǎn)，直到新點(diǎn)在左邊 int ConVexHull(Point* p,int n,Point*ch){sort(p,p+n);int m=0;for(int i=0;i<n;i++){//下凸包while(m>1 && Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;ch[m++]=p[i];}int k=m;for(int i=n-2;i>=0;i--){//上凸包while(m>k && Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;ch[m++]=p[i];}if(n>1)m--;return m; } //******************************************************************* int main(){int n,L;while(cin>>n>>L){Point p[1005],ch[1005];for(int i=0;i<n;i++) //輸入點(diǎn)cin>>p[i].x>>p[i].y;int m=ConVexHull(p,n,ch); //求解凸包并計(jì)算凸包周長(zhǎng)double sum=Length(ch[0]-ch[m-1]);for(int i=1;i<m;i++)sum+=Length(ch[i]-ch[i-1]);printf("%.0lf\n", sum+2*L*PI);//輸出周長(zhǎng)+圓周并四舍五入 }return 0; } View Code

?

總結(jié)

以上是生活随笔為你收集整理的[ACM_几何] Wall的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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