[POJ1113&POJ1696]凸包卷包裹算法和Graham扫描法应用各一例

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<R)and((cross(a[1],a[i],midx)>0)or((cross(a[1],a[i],midx)=0)and(dis[i]<midy))) do inc(i);
        while (L<j)and((cross(a[1],a[j],midx)<0)or((cross(a[1],a[j],midx)=0)and(dis[j]>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<R then qsort(i,R);
    if L<j then qsort(L,j);
end;

procedure Graham(n:longint;var len:longint);
var k,i:longint;
begin
    k:=0;a[0].x:=maxlongint;a[0].y:=maxlongint;
    for i:=1 to n do 
    if (a[i].y<a[k].y)or((a[i].y=a[k].y)and(a[i].x<a[k].x)) then k:=i;
    a[0]:=a[1];a[1]:=a[k];a[k]:=a[0];    
    for i:=2 to n do dis[i]:=getdis(a[i],a[1]);
    qsort(2,n);
    len:=3;stack[1]:=a[1];stack[2]:=a[2];stack[3]:=a[3];    
    for i:=4 to n do 
    begin
        while cross(stack[len-1],a[i],stack[len])>=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.

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)<getdis(a[k],s)))) then k:=j;
        write(a[k].id,‘ ‘);s:=a[k];vis[k]:=false;
    end;
end;

begin
    //assign(input,‘poj1696.in‘);reset(input);
    readln(test);
    for t:=1 to test do 
    begin
        readln(n);s.x:=0;s.y:=maxlongint;
        for i:=1 to n do     
        begin
            readln(a[i].id,a[i].x,a[i].y);
            if a[i].y<s.y then s.y:=a[i].y;
        end;
        Wrap(s);writeln;
    end;
end.