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

Обсуждение задачи 1130. Никифор на прогулке

wa37!!!!!!!!!!!!!!!!!!!!!!!
Послано Mikucon 26 мар 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.