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 1130. Nikifor's Walk

wa37!!!!!!!!!!!!!!!!!!!!!!!
Posted by Mikucon 26 Mar 2009 13:32
Program FLY_ural1130;
Const max=30000;
Var
 n,i,l,now,head:longint;
 p:array[1..max]of boolean;
 x,y,m,q,w,k:array[1..max]of longint;
Function check(f,u:longint):longint;
 var a,b,c:longint;
 begin
  a:=sqr(x[f])+sqr(y[f]);
  b:=sqr(x[u])+sqr(y[u]);
  c:=sqr(x[f]-x[u])+sqr(y[f]-y[u]);
  if (a+b-c)>sqrt(a*b)
   then exit(1)
   else if(a+b-c)<=-sqrt(a*b)
         then exit(2)
         else exit(3);
 end;
Procedure back(u:longint);
 begin
  if q[u]=0 then begin p[u]:=not p[u]; exit; end;
  back(q[u]);
  back(w[u]);
 end;
Procedure change_mod1(a,b:longint);
 begin
  inc(head);
  x[head]:=x[a]-x[b];
  y[head]:=y[a]-y[b];
  q[head]:=m[a]; w[head]:=m[b]; m[head]:=head;
  back(w[head]);
 end;
Procedure change_mod2(a,b:longint);
 begin
  inc(head);
  x[head]:=x[a]+x[b];
  y[head]:=y[a]+y[b];
  q[head]:=m[a]; w[head]:=m[b]; m[head]:=head;
 end;
Procedure exchange(a,b:longint);
 var u:longint;
 begin
  u:=x[a]; x[a]:=x[b]; x[b]:=u;
  u:=y[a]; y[a]:=y[b]; y[b]:=u;
  u:=m[a]; m[a]:=m[b]; m[b]:=u;
  u:=m[a]; m[a]:=m[b]; m[b]:=u;
  u:=q[a]; q[a]:=q[b]; q[b]:=u;
  u:=w[a]; w[a]:=w[b]; w[b]:=u;
 end;
Function checkzero(u:longint):boolean;
 begin
  if (x[u]=y[u])and(y[u]=0)
   then exit(true)
   else exit(false);
 end;
Begin
 {assign(input,'1130.in'); reset(input);
 assign(output,'1130.out'); rewrite(output); }
 readln(n,l); head:=n; now:=1;
 for i:=1 to n do
  begin readln(x[i],y[i]); p[i]:=true; m[i]:=i; end;
 while head>1+now  do
  begin
   if checkzero(now)
    then begin inc(now); continue; end;
   if checkzero(now+1)
    then begin
          inc(head); x[head]:=x[now]; y[head]:=y[now];
          m[head]:=m[now]; inc(now,2);
          continue;
         end;
   if checkzero(now+2)
    then begin
          inc(head); x[head]:=x[now]; y[head]:=y[now];
          m[head]:=m[now]; inc(now);
          inc(head); x[head]:=x[now]; y[head]:=y[now];
          m[head]:=m[now]; inc(now,2);
          continue;
         end;
   case check(now,now+1) of
    1:change_mod1(now,now+1);
    2:change_mod2(now,now+1);
    3:case check(now,now+2) of
       1:begin
          change_mod1(now,now+2);
         // exchange(now+1,now+2);
          inc(now);
          inc(head); x[head]:=x[now]; y[head]:=y[now];
          m[head]:=m[now];
         end;
       2:begin
          change_mod2(now,now+2);
          inc(now);
          inc(head); x[head]:=x[now]; y[head]:=y[now];
          m[head]:=m[now];
         end;
       3:case check(now+1,now+2) of
          1:begin
             change_mod1(now+1,now+2);
             inc(head); x[head]:=x[now]; y[head]:=y[now];
             m[head]:=m[now];
             inc(now);
            end;
          2:begin
             change_mod2(now+1,now+2);
            // exchange(now,now+2);
             inc(head); x[head]:=x[now]; y[head]:=y[now];
             m[head]:=m[now];
             inc(now);
            end;
         end;
      end;
   end;
   inc(now,2);
  end;
 if sqr(x[now]+x[head])+sqr(y[now]+y[head])>sqr(l)
  then back(m[head]);
 writeln('YES');
 for i:=1 to n do
  if p[i] then write('+') else write('-');
 close(output);
End.