凸包的算法比较形象好理解 代码写起来也比较短 所以考前看一遍应该就没什么问题了。。>_<
POJ1113
刚开始并没有理解为什么要用凸包,心想如果贴着城堡走不是更好吗?
突然发现题目中有要求在满足把所有点包括在内的情况下周长最短...这不就是凸包的性质吗?
而且显然如果城堡是凹的话,往里面绕一圈肯定会使周长增加...
然后可以从简单的三角形四边形推广出去,发现每个拐角-左右各90度之后所有的加和为180度
也就是在城堡周长的基础上再加一个半径为L的圆周长即是所求答案。
上次的模板写错了...应该是快排部分没有处理好...这次重新写的时候才发现...
program poj1113;
const pi=3.14159265358979;maxn=;
type point=record x,y:longint;end;
var i,n,l,len:longint;
ans:extended;
a:array[-..maxn]of point;
dis:array[-..maxn]of int64;
stack:array[-..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+)+L;
midx:=a[mid];midy:=dis[mid];
repeat
while (i<R)and((cross(a[],a[i],midx)>)or((cross(a[],a[i],midx)=)and(dis[i]<midy))) do inc(i);
while (L<j)and((cross(a[],a[j],midx)<)or((cross(a[],a[j],midx)=)and(dis[j]>midy))) do dec(j);
if i<=j then
begin
a[]:=a[i];a[i]:=a[j];a[j]:=a[];
dis[]:=dis[i];dis[i]:=dis[j];dis[j]:=dis[];
//之前的模板这里的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:=;a[].x:=maxlongint;a[].y:=maxlongint;
for i:= 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[]:=a[];a[]:=a[k];a[k]:=a[];
for i:= to n do dis[i]:=getdis(a[i],a[]);
qsort(,n);
len:=;stack[]:=a[];stack[]:=a[];stack[]:=a[];
for i:= to n do
begin
while cross(stack[len-],a[i],stack[len])>= do dec(len);
//要求边上的点也取的话就不能加等号
inc(len);stack[len]:=a[i];
end;
end; begin
//assign(input,'poj1113.in');reset(input);
readln(n,l);
for i:= to n do readln(a[i].x,a[i].y);
Graham(n,len);
ans:=sqrt(getdis(stack[],stack[len]));
//累计周长不能忘了第一个点和第n个点之间的边
//这里虽然容易检查出来但是希望下次累计长度的时候还是不要忘。。>_<
for i:= to len do ans:=ans+sqrt(getdis(stack[i],stack[i-]));
writeln(ans+*pi*l::);
end.
POJ1696
人生多艰...
话说好像还把在我后面评测的同学影响成了CE...QAQ
这道题只要不停地取满足条件的对于当前点最右边的点,当然要保证当前点右拐没有没取过的点。
首先肯定是都可以取到的,然后用卷包裹不停地取就好了...
这题唯一需要修改的就是取过的点要打标记,然后就轻松AC啦~
program poj1696;
const maxn=;
type point=record x,y,id:longint;end;
var t,test,i,n:longint;
a:array[-..maxn]of point;
vis:array[-..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:= to n do
begin
for j:= to n do if vis[j] then begin k:=j;break;end;
// 刚开始TOO NAIVE...给k的初值赋为0,然后0节点搞了个(0,1000),后来发现这满足刚开始的条件QAQ
// 为了维护世界的和平...还是尽量不要用没有出现过的点好了...
for j:= to n do if (vis[j])and((cross(s,a[j],a[k])>)or((cross(s,a[j],a[k])=)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:= to test do
begin
readln(n);s.x:=;s.y:=maxlongint;
for i:= 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.