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 1163. Chapaev

Please help me(+)
Posted by Nazarov Denis (nsc2001@rambler.ru) 20 Mar 2002 00:29
I get AC with this program. But it's wrong! Please give me some hints
to solve this problem or Accepted program (not as my) :-))

{$A-,B-,D+,E+,F-,G-,I-,L+,N+,O-,P-,Q-,R-,S-,T-,V-,X-}
Program t1163;

Const  Radius = 0.4;
       Change = Pi/180;
       N      = 8;
       L      = 8;
       Eps    = 1E-5;

Type Point  = record X,Y : extended end;
     Vector = record rX,rY : extended end;
     IMas   = array[1..N]of byte;

Var  R,W           : array[1..N]of Point;
     Ru,Wu         : IMas;
     i             : integer;
     count         : integer;

Function GetW(A : Vector) : extended;
Var tgW,W  : extended;
 begin
  if abs(A.rX)=0 then begin
    if A.rY<0 then W:=270 else W:=90;
   end else
  if abs(A.rY)=0 then begin
    if A.rX<0 then W:=180 else W:=0;
   end else begin
    tgW:=Abs(A.rY/A.rX);
    W:=ArcTan(tgW); W:=W/Change;
    if (A.rX<0)and(A.rY>0) then W:=180-W;
    if (A.rX<0)and(A.rY<0) then W:=180+W;
    if (A.rX>0)and(A.rY<0) then W:=360-W;
   end;
  GetW:=W;
 end;

Function GetWT(a,b,c : extended) : extended;
Var cosw,sinw,tgw,w   : extended;
 begin
  cosw:=(b*b+c*c-a*a)/(2*b*c);
  sinw:=sqrt(abs(1-cosw*cosw));
  if abs(cosw)<Eps then
   w:=90
  else begin
   tgw:=sinw/cosw;
   w:=ArcTan(tgw);
   w:=w/Change;
  end;
  GetWT:=w;
 end;

Function Dist(A,B : Point) : extended;
 begin
  Dist:=sqrt(sqr(A.X-B.X)+sqr(A.Y-B.Y));
 end;

Function Touch(begP,tP : Point; wF : extended) : boolean;
Var TVector      : Vector;
    w,aw,d,dp    : extended;
 begin
  TVector.rX:=begP.X-tP.X;
  TVector.rY:=begP.Y-tP.Y;
  w:=GetW(TVector);
  aw:=abs(w-wF);
  if aw>180 then aw:=360-aw;
  aw:=aw*Change;
  dp:=Dist(begP,tP);
  d:=sqrt(2*dp*dp*(1-cos(aw)));
  Touch:= d<=2*Radius;
 end;

Function WinGR : boolean; forward;
Function WinGW : boolean; forward;

Function WinGW : boolean;
var i,j      : integer;
    u,v,vv   : integer;
    wh1,re1  : integer;
    A        : Vector;
    w1,dw,d  : extended;
    wFLICK   : extended;
    Tr,Tw    : IMas;
    ok       : byte;
    pp       : array[1..2*n*n]of IMas;
 begin
  inc(count);
// SEE AT THIS
// IF COUNT>10000 I
//   WRITE
//  'RED' !!
//
  if count>100000 then begin
    Writeln('RED');
    Halt;
   end;
  vv:=0;
  for i:=1 to N do if Wu[i]=0 then
   for j:=N downto 1 do if Ru[j]=0 then begin
    A.rx:=W[i].X-R[j].X;
    A.ry:=W[i].Y-R[j].Y;
    w1:=GetW(A);
    d:=Dist(W[i],R[j]);
    dw:=GetWT(2*Radius,d,d);
    Wu[i]:=1;
    Tr:=Ru; Tw:=Wu;
    {go down}
    wFLICK:=w1-dw; if wFLICK<0 then wFLICK:=wFLICK+360;
    wh1:=0; re1:=0;
    for u:=1 to N do if Wu[u]=0 then if Touch(W[i],W[u],wFLICK) then
begin Wu[u]:=1; inc(wh1); end;
    for u:=1 to N do if Ru[u]=0 then if Touch(W[i],R[u],wFLICK) then
begin Ru[u]:=1; inc(re1); end;
    ok:=1;
    for u:=1 to vv do begin
      ok:=0;
      for v:=1 to 8 do if pp[u][v]<ru[v] then ok:=1;
      if ok=1 then break;
     end;
    if wh1<re1 then
    if ok=1 then begin
     inc(vv);
     for u:=1 to 8 do pp[vv][u]:=ru[u];
    if not(WinGR) then begin
      WinGW:=true;
      Wu[i]:=0;
      exit;
     end;
    end;
    Ru:=Tr; Wu:=Tw;
    {go up}
    wFLICK:=w1+dw; if wFLICK>360 then wFLICK:=wFLICK-360;
    wh1:=0; re1:=0;
    for u:=1 to N do if Wu[u]=0 then if Touch(W[i],W[u],wFLICK) then
begin Wu[u]:=1; inc(wh1); end;
    for u:=1 to N do if Ru[u]=0 then if Touch(W[i],R[u],wFLICK) then
begin Ru[u]:=1; inc(re1); end;
    ok:=1;
    for u:=1 to vv do begin
      ok:=0;
      for v:=1 to 8 do if pp[u][v]<ru[v] then ok:=1;
      if ok=1 then break;
     end;
    if ok=1 then begin
     inc(vv);
     for u:=1 to 8 do pp[vv][u]:=ru[u];
    if wh1<re1 then
    if not(WinGR) then begin
      WinGW:=true;
      Wu[i]:=0;
      exit;
     end;
    end;
    Ru:=Tr; Wu:=Tw;