ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1173. Lazy Snail

Posted by xzl 21 Feb 2002 06:21
const
limit        =1000;

type
Tnode        =record
id         :integer;
dig        :extended;
end;

var
s            :array[1..limit] of Tnode;
n            :integer;

procedure init;
var
x,y,bx,by    :extended;
i            :integer;
begin
for i:=1 to n do
with s[i] do
begin
x:=x-bx;y:=y-by;dig:=abs(y)/sqrt(x*x+y*y);
if y>0 then
if x>0 then dig:=1-dig
else dig:=3+dig
else if x>0 then dig:=1+dig
else dig:=3-dig
end;
end;

procedure sift(p,tot:integer);
var
i,q          :integer;
d            :extended;
begin
i:=s[p].id;d:=s[p].dig;
while true do
begin
q:=p+p;
if (q<tot) and (s[q].dig<s[q+1].dig) then inc(q);
if (q>tot) or (s[q].dig<d) then begin s[p].id:=i;s[p].dig:=d;exit;
end;
s[p]:=s[q];p:=q;
end;
end;

procedure work;
var
temp         :Tnode;
i            :integer;
begin
for i:=n div 2 downto 1 do sift(i,n);
for i:=n downto 1 do
begin
temp:=s[i];
s[i]:=s[1];
s[1]:=temp;
sift(1,i-1);
end;
end;

procedure out;
var
i            :integer;
begin
writeln(0);
for i:=1 to n do writeln(s[i].id);
writeln(0);
end;

BEGIN
init;
work;
out;
END.