POJ1113Wall

转载请注明出处：優YoU http://user.qzone.qq.com/289065406/blog/1303097935

大致题意：

给定多边形城堡的n个顶点，绕城堡外面建一个围墙，围住所有点，并且墙与所有点的距离至少为L，求这个墙最小的长度。

解题思路：

推导公式（1）：

城堡围墙长度最小值 = 城堡顶点坐标构成的散点集的凸包总边长 + 半径为L的圆周长

由于数据规模较大，必须用GrahamScan Algorithm构造凸包（详细的算法可以参考我的POJ2187，这里就不再啰嗦了），然后顺序枚举凸包相邻的两点并计算其距离，得到凸包的总边长，最后加上圆周长2πL

根据圆形的性质,其实就相当于多加了一个r=L的圆，把该圆根据凸包的边数（假设有k条）划分为k段弧，分别用来连接凸包上所有边。这样做的目的就是为了在保证围墙距离城堡至少为L的同时，使得转角处为圆角而不是直角，减少建造围城所需的资源。

附：

针对上面的公式（1）copy一个证明：http://blog.sina.com.cn/s/blog_687916bf0100jq9g.html

证明如下：假如顺时针给出四个点A、B、C、D。组成了凸四边形ABCD。我们不妨过A点作AE垂直于AB，同时过A点再作AF垂直于AD，过B点作BG、BH分别垂直于AB、BC。连结EG，垂线段的长度为L，过A点以AE为半径作一段弧连到AF，同理，使GH成为一段弧。此时EG=AB（边），AB段城墙的最小值为EF+弧EF+弧GH=AB+弧EF+弧GH。对所有点进行同样的操作后，可知城墙的最小值=四边形的周长+相应顶点的弧长（半径都为L）之和。

下面证明这些顶点弧长组成一个圆。依然以前面的四边形为例。A、B、C、D四顶点各成周角，总和为360*4=1440度，四边形内角和为360度，每个顶点作两条垂线，总角度为4*2*90=720度，所以总圆周角为1440-360-720=360度，刚好组成圆。

所以四边形ABCD的围墙最短= 四边形的周长+圆周长。

推广到任意多边形，用同样的方法，城墙最短=凸包的周长 + 以L为半径的圆的周长。

首先，我们得出城墙最短=凸包的周长 + 相应顶点的弧长（半径都为L）之和。

再证明相应顶点的弧长（半径都为L）之和=以L为半径的圆的周长。

事实上，设凸包顶点为n,n个顶点组成n个周角，角度为360*n=2*180*n，凸包的内角和为180*(n-2)，作了2*n条垂线，和为2*n*90=180*n,所以总圆周角为2*180*n-180*(n-2)-180*n=360，组成圆。

  1 //Memory Time 
  2 //244K   63MS 
  3 
  4 #include<iostream>
  5 #include<cmath>
  6 #include<iomanip>
  7 using namespace std;
  8 
  9 const int inf=10001;
 10 const double pi=3.141592654;
 11 
 12 typedef class
 13 {
 14     public:
 15         int x,y;
 16 }point;
 17 
 18 /*AB距离平方*/
 19 
 20 int distsquare(point A,point B)
 21 {
 22     return (B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y);
 23 }
 24 
 25 /*AB距离*/
 26 
 27 double distant(point A,point B)
 28 {
 29     return sqrt((double)((B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y)));
 30 }
 31 
 32 /*叉积计算*/
 33 
 34 int det(int x1,int y1,int x2,int y2)
 35 {
 36     return x1*y2-x2*y1;
 37 }
 38 
 39 int cross(point A,point B,point C,point D)
 40 {
 41     return det(B.x-A.x,B.y-A.y,D.x-C.x,D.y-C.y);
 42 }
 43 
 44 /*快排判断规则*/
 45 
 46 point* s;
 47 int cmp(const void* pa,const void* pb)
 48 {
 49     point* a=(point*)pa;
 50     point* b=(point*)pb;
 51 
 52     int temp=cross(*s,*a,*s,*b);
 53     if(temp>0)
 54         return -1;
 55     else if(temp==0)
 56         return distsquare(*s,*b)-distsquare(*s,*a);
 57     else
 58         return 1;
 59 }
 60 
 61 int main(int i,int j)
 62 {
 63     int N,L;
 64     while(cin>>N>>L)
 65     {
 66         /*Input*/
 67 
 68         point* node=new point[N+1];
 69 
 70         int min_x=inf;
 71         int fi;
 72         for(i=1;i<=N;i++)
 73         {
 74             cin>>node[i].x>>node[i].y;
 75 
 76             if(min_x > node[i].x)
 77             {
 78                 min_x = node[i].x;
 79                 fi=i;
 80             }
 81             else if(min_x == node[i].x)
 82                 if(node[fi].y > node[i].y)
 83                     fi=i;
 84         }
 85 
 86         /*Quicksort the Vertex*/
 87 
 88         node[0]=node[N];
 89         node[N]=node[fi];
 90         node[fi]=node[0];
 91 
 92         s=&node[N];
 93         qsort(node+1,N,sizeof(point),cmp);
 94 
 95         /*Structure Con-bag*/
 96 
 97         int* bag=new int[N+2];
 98         bag[1]=N;
 99         bag[2]=1;
100         int pb=2;
101         for(i=2;i<=N;)
102             if(cross(node[ bag[pb-1] ],node[ bag[pb] ],node[ bag[pb] ],node[i]) >= 0)
103                 bag[++pb]=i++;
104             else
105                 pb--;
106 
107         /*Compute Min-length*/
108 
109         double minlen=0;
110         for(i=1;i<pb;i++)
111             minlen+=distant(node[ bag[i] ],node[ bag[i+1] ]);
112 
113         minlen+=2*pi*L;
114 
115         cout<<fixed<<setprecision(0)<<minlen<<endl;
116 
117         delete node;
118         delete bag;
119     }
120     return 0;
121 }