題目鏈接：http://poj.org/problem?id=1113

題意：一個國王要在自己的城堡周圍建一堵圍墻，要求圍墻距城堡最短距離為L。問建這樣一堵圍墻的最短長度是多少。

?

題解思路：顯然圍墻建的距城堡越近越好，這樣對于城堡的邊我們沿著城堡距離L的地方建就可以了，對于城堡的頂點，我們以頂點為圓心，以L為半徑畫一段圓弧。易之圍墻的周長即為圓弧和+沿城堡建的圍墻的和。

但題目并沒說給的多變形就是凸多邊形。顯然如果是凸多邊形的話，直接用上面的方法計算即可。而對于凹多邊形凹的部分如果我們也像上面的做法那樣沿著城堡的邊建圍墻，頂點畫圓弧，然后兩者再加起來的話顯然是錯誤的，因為我們知道兩點之間直線最短，這樣做得到的邊長和顯然要大于兩點間的直線段的和！所以對于凹多邊形，我們的做法是用一條線段直接將凹下去兩點連起來，使之成為一個凸包。所以這樣題目就很簡單了，直接用掃描法構造凸包，將其中凹下去的部分舍掉即可。

?

還有一點，凸多邊形的外角和等于360度，所以所有圓弧的部分加起來就是一個園。所以最后圍墻的最短周長就是：構造的凸多邊形的周長+半徑為L的園的周長。

?

此題題目有點誤導人，題意已經指出城堡的頂點以順時針給出，但實際的數據并不是按序給出的！所以先要自己排好序，再構建凸包。（有點坑爹。。。害我WA了好幾次。。。）

AC 代碼：

View Code 1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 using namespace std; 6 #define pi acos(-1) 7 #define eps 1e-8 8 using namespace std; 9 const int N=1005; 10 struct point{ 11 double x,y; 12 }pt[N]; 13 int con[N]; 14 int n,l,tot; 15 double dist(point a,point b){ 16 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 17 } 18 double xmult(point p0,point p1,point p2){ 19 double x1=p1.x-p0.x; 20 double y1=p1.y-p0.y; 21 double x2=p2.x-p0.x; 22 double y2=p2.y-p0.y; 23 return (x1*y2-x2*y1); 24 } 25 bool cmp(point a,point b){ 26 if(xmult(pt[0],a,b)>0||xmult(pt[0],a,b)==0&&(dist(a,pt[0])<dist(b,pt[0])))return true; 27 return false; 28 } 29 void graham(){ 30 sort(pt+1,pt+n,cmp); 31 tot=0; 32 con[tot++]=0; 33 con[tot++]=1; 34 for(int i=2;i<n;){ 35 if(tot<1||xmult(pt[con[tot-2]],pt[con[tot-1]],pt[i])>=0) 36 con[tot++]=i++; 37 else tot--; 38 } 39 con[tot]=0; 40 } 41 int main() 42 { 43 //freopen("in.txt","r",stdin); 44 int i,k; 45 double ans; 46 while(scanf("%d %d",&n,&l)!=EOF){ 47 k=n-1; 48 for(i=n-1;i>=0;i--){ 49 scanf("%lf %lf",&pt[i].x,&pt[i].y); 50 if(pt[i].y<pt[k].y||((pt[i].y==pt[k].y)&&(pt[i].x<pt[k].x))) 51 k=i; 52 } 53 if(k){ 54 swap(pt[0].x,pt[k].x); 55 swap(pt[0].y,pt[k].y); 56 } 57 graham(); 58 ans=0; 59 for(i=0;i<tot;i++) 60 ans+=dist(pt[con[i]],pt[con[i+1]]); 61 ans+=2*pi*l; 62 printf("%d\n",(int)(ans+0.5)); 63 } 64 return 0; 65 }

?

?

轉載于:https://www.cnblogs.com/acmer-roney/archive/2012/09/04/2670534.html

總結

以上是生活随笔為你收集整理的wall poj 1113的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。