|
|
back to boardDiscussion of Problem 1185. WallLittle 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 . Epsilon is not needed for this problem (-) > 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 if vp<eps then here it means vp<=0 when eps=0.00000000001 and vp<0 when eps=0 |
|
|