ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1185. Wall

Crash!
Posted by lzoi_HsWy 29 Dec 2002 10:59
program p1185;
const maxx=1000;
type rec=record x,y:integer; end;
     arr=array [1..maxx] of rec;
var tdot,dot:arr; n,l:integer; s:extended;

{$APPTYPE CONSOLE}

procedure init;
var i:integer;
begin
     readln(n,l);
     for i:=1 to n do readln(tdot[i].y,tdot[i].x);
end;

procedure solve;
var i:integer;
   function multi(a,b,c:rec):integer;
   begin
        multi:=(a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
   end;
   procedure find(n:integer);
   var i:integer; t:rec;
   begin
        for i:=1 to n do
          if (tdot[i].y<tdot[1].y) or ((tdot[i].y=tdot[1].y) and (tdot
[i].x<tdot[i].x)) then
            begin
              t:=tdot[i]; tdot[i]:=tdot[1]; tdot[1]:=t;
            end;
   end;
   procedure scan(k:integer);
   var stack:array [1..maxx] of integer; i,top:integer;
   begin
        for i:=1 to 3 do stack[i]:=i; top:=3;
        for i:=4 to k do
          begin
            while (multi(tdot[i],tdot[stack[top]],tdot[stack[top-1]])
>0) do dec(top);
            inc(top);
            stack[top]:=i;
          end;
        for i:=1 to top do dot[i]:=tdot[stack[i]]; n:=top;
   end;
   function gg(a,b:rec):extended;
   begin
        gg:=sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
   end;
begin
     find(n);
     scan(n);
     for i:=1 to (n-1) do
       begin
         s:=s+gg(dot[i],dot[i+1]);
       end;
     s:=s+gg(dot[n],dot[1]);
     s:=s+l*2*pi;
end;

procedure sout;
begin
     writeln(s:0:0);
end;

begin
     init;
     solve;
     sout;
end.
Crash, too!! help!!!
Posted by 永遠の痛 12 Aug 2003 09:06
it is as same as ZJU1465 :(
I got RuntimeError201 there...


{$N+}
const
     maxn=1001;

type
    postype=record
                  x,y:double;
    end;

var
   ti,tn,n,top:longint;
   list:array[0..maxn] of postype;
   stk:array[1..maxn] of longint;
   feet:double;

procedure swap(var a,b:postype);
var
   t:postype;

begin
     t:=a;
     a:=b;
     b:=t;
end;

function multi(var p1,p2,p0:postype):double;
begin
     multi:=(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
end;

function comp(var p1,p2:postype):boolean;
var
   t:double;

begin
     t:=multi(p1,p2,list[0]);
     if (t>0) or (t=0) and (sqr(p1.x-list[0].x)+sqr(p1.y-list[0].y)<
     sqr(p2.x-list[0].x)+sqr(p2.y-list[0].y)) then
                                              comp:=true
     else                                     comp:=false;
end;

procedure sort(p,r:longint);
var
   i,j:longint;
   x:postype;

begin
     if r-p+1<=5 then
        begin
             for j:=p+1 to r do
                 begin
                      i:=j;
                      while (i>1) and (comp(list[i],list[i-1])) do
                            begin
                                 swap(list[i],list[i-1]);
                                 dec(i);
                            end;
                 end;
        end
     else
         begin
              x:=list[p+random(r-p+1)];
              i:=p;
              j:=r;
              repeat
                    while comp(list[i],x) do inc(i);
                    while comp(x,list[j]) do dec(j);
                    if i<j then swap(list[i],list[j]);
              until i>=j;
              sort(p,j);
              sort(j+1,r);
         end;
end;

procedure init;
var
   i:longint;

begin
     readln(n,feet);
     if n=0 then halt;
     for i:=0 to n-1 do
         begin
              readln(list[i].x,list[i].y);
              if (list[i].y<list[0].y) or ((list[i].y=list[0].y) and
(list[i].x<list[0].x)) then
                 swap(list[0],list[i]);
         end;
     sort(1,n-1);
end;

procedure graham;
var
   i:longint;
   d:double;

begin
     for i:=1 to 3 do
         stk[i]:=i-1;
     top:=3;

     for i:=3 to n-1 do
         begin
              while multi(list[i],list[stk[top]],list[stk[top-1]])>=0
do
                    dec(top);
              inc(top);
              stk[top]:=i;
         end;

     d:=0;
     for i:=1 to top-1 do
         d:=d+ sqrt ( (list[stk[i]].x-list[stk[i+1]].x)*(list[stk
[i]].x-list[stk[i+1]].x) +
         (list[stk[i]].y-list[stk[i+1]].y)*(list[stk[i]].y-list[stk
[i+1]].y));

         d:=d+ sqrt ( (list[stk[top]].x-list[stk[1]].x)*(list[stk
[top]].x-list[stk[1]].x)
                    + (list[stk[top]].y-list[stk[1]].y)*(list[stk
[top]].y-list[stk[1]].y));

     writeln(round(d+feet*3.141592653*2));
end;

begin
     assign(input,'1465.in');
     reset(input);
     readln(tn);
     for ti:=1 to tn do
         begin
              init;
              graham;
              if ti<>tn then writeln;
         end;
end.