Архив форума

Я наверно сильно тупой. Граждане уральцы помогите мудрым словом.
Я придумал тупую идею. Мне почему-то кажется, что если решение существует, то существует и такое решение в котором две тарелки "зажаты" в углах. Это типа первое тонкое место.
Что я делаю. Я перебираю все пары тарелок, и ставлю их в углы. А третью тарелку нада куда-то запихать. Для этого я рассматриваю прямоугольник, который получается сжиманием исходного на R c каждой стороны. Понятно что центр третьей окружности должен находиться где-то в нем. Пусть (х1,у1) и (х2,у2) - центры окружностей, которые мы уже поставили. Тогда центр третьей окружности должен быть не ближе чем R+R1 и R+R2 от этих точек (типа 2 окружности получаются) соответственно (иначе веть тарелки наложатся). Ну вот я и перебираю все точки пересечения этих окружностей со сторонами прямоугольника и проверяю "встает ли 3я тарелка нормально или нет". Никакие точки внутри прямоугольника я не проверяю. Это второе тонкое место... хотя врят ли... Дайте мне тестов хитрых или покажите где я дурак. Вот если кому интересно прога моя:

Const Eps = 0.00000000000001;



Type MyLine = record

                X0, Y0, Vx, Vy : extended; {Vx, Vy - направление прямой}

              End;

     MyCircle = record

                  X, Y, R : extended;

                End;



Var W, H                   : extended;

    X,Y                    : array [1..30] of extended;

    Xans, Yans, R          : array [1..3] of extended;

    NP                     : longint;

    L                      : array [1..4] of MyLine;

    C                      : array [1..2] of MyCircle;



Function Dist(x1,y1,x2,y2 : extended) : extended;

Begin

  Dist:=sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));

End;



Function SatisfiesTask : boolean;

var Res : boolean;

    i   : longint;

Begin

  res:=true;

  For i:=1 to 3 do Begin

    res:=Res AND (R[i]-Xans[i]<eps);

    res:=Res AND (R[i]-Yans[i]<eps);

    res:=res AND (Xans[i]-W+R[i]<eps);

    res:=res AND (Yans[i]-H+R[i]<eps);

  End;

  res:=res AND (R[1]+R[2]-Dist(Xans[1], Yans[1],Xans[2], Yans[2])<eps);

  res:=res AND (R[1]+R[3]-Dist(Xans[1], Yans[1],Xans[3], Yans[3])<eps);

  res:=res AND (R[3]+R[2]-Dist(Xans[3], Yans[3],Xans[2], Yans[2])<eps);

  SatisfiesTask:=res;

End;



Procedure CrossCircleAndLine(Var cir : MyCircle; Var lin : MyLine);

Var T, Tx, Ty, D, Dt     : extended;

Begin

  T:=lin.Vx*(cir.X-lin.X0) + lin.Vy*(cir.Y-lin.Y0);

  Tx:=lin.X0 + lin.Vx*T;   Ty:=lin.y0 + lin.Vy*T;

  D:=Dist(Tx, Ty, cir.X, cir.Y);

  If D-cir.R<eps then Begin

    Dt:=Sqrt( Abs(cir.R*cir.R-D*D) );

    Inc(Np); X[np]:= lin.X0 + lin.Vx*(T-dt); Y[np]:= lin.Y0 + lin.VY*(T-dt);

    Inc(Np); X[np]:= lin.X0 + lin.Vx*(T+dt); Y[np]:= lin.Y0 + lin.VY*(T+dt);

  End;

End;



Procedure TrySolve(n1, n2 : longint);

var i1, i2, i3 : Longint;

    Rn         : extended;

Begin

  Rn:=R[6-n1-n2];

  L[1].X0:=Rn;   L[1].Y0:=Rn;   L[1].Vx:=1; L[1].Vy:=0;

  L[2].X0:=Rn;   L[2].Y0:=Rn;   L[2].Vx:=0; L[2].Vy:=1;

  L[3].X0:=W-Rn; L[3].Y0:=H-Rn; L[3].Vx:=1; L[3].Vy:=0;

  L[4].X0:=W-Rn; L[4].Y0:=H-Rn; L[4].Vx:=0; L[4].Vy:=1;



  For i1:=1 to 4 do {для каждой из окр-тей перебираем угол}

  For i2:=1 to 4 do

  If (1=1) then Begin

    If i1 in [1,3] then Xans[n1]:=R[N1] else Xans[n1]:=W-R[n1];

    If i2 in [1,3] then Xans[n2]:=R[N2] else Xans[n2]:=W-R[n2];

    If i1 in [1,2] then Yans[n1]:=R[N1] else Yans[n1]:=H-R[n1];

    If i2 in [1,2] then Yans[n2]:=R[N2] else Yans[n2]:=H-R[n2];



    C[1].X:=Xans[n1]; C[1].Y:=Yans[n1]; C[1].R:=R[n1]+R[6-n1-n2];

    C[2].X:=Xans[n2]; C[2].Y:=Yans[n2]; C[2].R:=R[n2]+R[6-n1-n2];



    NP:=0;

    For i3:=1 to 4 do CrossCircleAndLine(C[1], L[i3]);

    For i3:=1 to 4 do CrossCircleAndLine(C[2], L[i3]);

    Inc(NP); X[NP]:=Rn; Y[Np]:=Rn;

    Inc(NP); X[NP]:=Rn; Y[Np]:=H-Rn;

    Inc(NP); X[NP]:=W-Rn; Y[Np]:=Rn;

    Inc(NP); X[NP]:=W-Rn; Y[Np]:=H-Rn;

    For i3:=1 to NP do Begin

      Xans[6-n1-n2]:=X[i3];

      Yans[6-n1-n2]:=Y[i3];

      If SatisfiesTask then Begin

        Writeln(Xans[1]:0:4,' ',Yans[1]:0:4,' ',Xans[2]:0:4,' ',Yans[2]:0:4,' ',Xans[3]:0:4,' ',Yans[3]:0:4);

        Halt(0);

      End;

    End;

  End;

End;



begin

  { TODO -oUser -cConsole Main : Insert code here }

  Read(W, H, R[1], R[2], R[3]);



  TrySolve(1,2);

  TrySolve(1,3);

  TrySolve(2,3);

  Writeln('0');

end.

Неправда! На разборе этой задачи приводился контр-пример.

Спасиба, осознал. 8-)
Попробую я их рекурсивно распихивать...
А разбор задач в инет выложили? Где??? 8-)

Ага - сдалась... :D

Ничего страшного. Автор и рецензент тоже долго так думали, пока не прозрели. Слава Богу, это произошло до контеста, а не во время.