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

Little question
Posted by AIT 14 Mar 2003 22:28

const eps = 0;
type real = extended;
type tpoint = record x, y: real; end;
var n, l: longint;
    mas: array [1..1000] of tpoint;
    an: array [1..1000] of real;
    ob: array [1..1000] of boolean;
    ans: array [1..1000] of longint;
    a, ang: real;
    i, j, k: longint;
    c, t: tpoint;
    v: array [1..3] of longint;
function getan(p: tpoint): real;
var x: real;
begin
     if p.x=0 then
     begin
          if p.y>0 then getan:=pi/2 else getan:=-pi/2;
          exit;
     end;
     x:=p.y/p.x;
     getan:=arctan(x);
end;
procedure fconvex;
var vp: real;
    v1, v2: tpoint;
begin
     v[1]:=2;
     v[2]:=3;
     v[3]:=4;
     i:=4;
     repeat
          v1.x:=mas[v[2]].x-mas[v[1]].x; v1.y:=mas[v[2]].y-mas[v
[1]].y;
          v2.x:=mas[v[3]].x-mas[v[2]].x; v2.y:=mas[v[3]].y-mas[v
[2]].y;
          vp:=v1.x*v2.y-v1.y*v2.x;
          if vp<eps then
          begin
               ob[v[2]]:=false;
               dec(k);
               v[2]:=v[1];
               dec(v[1]);
               while ob[v[1]]= false do dec(v[1]);
          end else
          begin
               v[1]:=v[2]; v[2]:=v[3]; i:=i mod n + 1; v[3]:=i;
          end;
     until i=2;
end;
begin
          read(n, l);
     c.x:=maxlongint;
     c.y:=maxlongint;
     fillchar(ob, sizeof(ob), false);
     for i:=1 to n do
     begin
          read(mas[i].x, mas[i].y);
          if (mas[i].x<c.x)or((mas[i].y<c.y)and(mas[i].x=c.x)) then
c:=mas[i];
     end;
     for i:=1 to n do
     begin
          t.x:=mas[i].x-c.x;t.y:=mas[i].y-c.y;
          an[i]:=getan(t);
          j:=i;
          while (j>1)and(an[j]<an[j-1]) do
          begin
                a:=an[j];
                an[j]:=an[j-1];
                an[j-1]:=a;
                t:=mas[j];
                mas[j]:=mas[j-1];
                mas[j-1]:=t;
                dec(j);
          end;
     end;
     fillchar(ob, sizeof(ob), true);
     k:=n;
     if n>3 then
     fconvex;
     i:=1;
     j:=0;
     repeat
          while (i<n)and(not ob[i]) do inc(i);
          inc(j);
          ans[j]:=i;
          inc(i);
     until j=k;
     a:=0;
     for i:=1 to k-1 do
     begin
          ang:=sqr(mas[ans[i]].x-mas[ans[i+1]].x)+sqr(mas[ans[i]].y-
mas[ans[i+1]].y);
          ang:=sqrt(ang);
          a:=a+ang;
     end;
     ang:=sqrt(sqr(mas[ans[k]].x-mas[ans[1]].x)+sqr(mas[ans[k]].y-mas
[ans[1]].y));
     a:=a+ang;
     a:=a+2*pi*l;
     writeln(a:0:0);
end.


Why my solution works if eps=0 and doesn't work if eps is for example
0.00000000001
i think because test dataes has calculated by eps=0 .
Posted by Locomotive 14 Mar 2003 22:32
Epsilon is not needed for this problem (-)
Posted by Miguel Angel 15 Mar 2003 07:47
>
Thanks, but...
Posted by AIT 16 Mar 2003 23:48
It doesn't used for accuracy in calculations ( i ask why <=0 doesn't
work )
Re: Little question
Posted by currently unnamed... 1 Apr 2006 20:55
if vp<eps then

here it means vp<=0 when eps=0.00000000001
and vp<0 when eps=0