ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1185. Wall

Crash!
Послано lzoi_HsWy 29 дек 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!!!
Послано 永遠の痛 12 авг 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.