凸包的算法比较形象好理解 代码写起来也比较短 所以考前看一遍应该就没什么问题了。。>_<

---

 

POJ1113

　　刚开始并没有理解为什么要用凸包，心想如果贴着城堡走不是更好吗？

　　突然发现题目中有要求在满足把所有点包括在内的情况下周长最短...这不就是凸包的性质吗？

　　而且显然如果城堡是凹的话，往里面绕一圈肯定会使周长增加...

　　然后可以从简单的三角形四边形推广出去，发现每个拐角-左右各90度之后所有的加和为180度

　　也就是在城堡周长的基础上再加一个半径为L的圆周长即是所求答案。

　　上次的模板写错了...应该是快排部分没有处理好...这次重新写的时候才发现...

program poj1113;const pi=3.14159265358979;maxn=1010;type point=record x,y:longint;end;var i,n,l,len:longint;     ans:extended;     a:array[-1..maxn]of point;     dis:array[-1..maxn]of int64;     stack:array[-1..maxn]of point;function getdis(a,b:point):int64;begin    exit(sqr(a.x-b.x)+sqr(a.y-b.y));end;function cross(p0,p1,p2:point):int64;begin    exit((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));end;procedure qsort(L,R:longint);var i,j,mid:longint;      midy:int64;      midx:point;begin    i:=L;j:=R;mid:=random(R-L+1)+L;    midx:=a[mid];midy:=dis[mid];    repeat        while (i
     
      0)or((cross(a[1],a[i],midx)=0)and(dis[i]
      
       midy))) do dec(j);        if i<=j then        begin            a[0]:=a[i];a[i]:=a[j];a[j]:=a[0];            dis[0]:=dis[i];dis[i]:=dis[j];dis[j]:=dis[0];            //之前的模板这里的dis数组没有交换，那道题是平面最远点对的...就导致取错了点。            inc(i);dec(j);        end;    until i>j;    if i
       
        =0 do dec(len);        //要求边上的点也取的话就不能加等号        inc(len);stack[len]:=a[i];    end;end;begin    //assign(input,'poj1113.in');reset(input);        readln(n,l);    for i:=1 to n do readln(a[i].x,a[i].y);    Graham(n,len);    ans:=sqrt(getdis(stack[1],stack[len]));    //累计周长不能忘了第一个点和第n个点之间的边    //这里虽然容易检查出来但是希望下次累计长度的时候还是不要忘。。>_<        for i:=2 to len do ans:=ans+sqrt(getdis(stack[i],stack[i-1]));        writeln(ans+2*pi*l:0:0);end.
       
      
     

 

---

 

POJ1696

　　人生多艰...

　　话说好像还把在我后面评测的同学影响成了CE...QAQ 

　　这道题只要不停地取满足条件的对于当前点最右边的点，当然要保证当前点右拐没有没取过的点。

　　首先肯定是都可以取到的，然后用卷包裹不停地取就好了...

　　这题唯一需要修改的就是取过的点要打标记，然后就轻松AC啦~

 

program poj1696;const maxn=55;type point=record x,y,id:longint;end;var t,test,i,n:longint;      a:array[-1..maxn]of point;      vis:array[-1..maxn]of boolean;      s:point;function cross(p0,p1,p2:point):longint;begin    exit((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));end;function getdis(a,b:point):longint;begin    exit(sqr(a.x-b.x)+sqr(a.y-b.y));end;procedure Wrap(s:point);var i,j,k:longint;begin    fillchar(vis,sizeof(vis),true);    write(n,' ');    for i:=1 to n do     begin        for j:=1 to n do if vis[j] then begin k:=j;break;end;        // 刚开始TOO NAIVE...给k的初值赋为0，然后0节点搞了个（0,1000），后来发现这满足刚开始的条件QAQ        // 为了维护世界的和平...还是尽量不要用没有出现过的点好了...        for j:=1 to n do if (vis[j])and((cross(s,a[j],a[k])>0)or((cross(s,a[j],a[k])=0)and(getdis(a[j],s)